#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(), (x).end()
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
string s;
cin >> s;
// Init Jumpings
vvi next_loc(n, vi(10, n));
int cntE = 0; // der letzte und erste Buchstabe sind != 'e'
for (int i = n - 2; i >= 0; --i)
{
for (int c = 0; c < 10; ++c)
next_loc[i][c] = next_loc[i + 1][c];
next_loc[i][s[i + 1] - 'a'] = i + 1;
if (s[i + 1] == 'e')
++cntE;
}
// make dp
vvi dp(n, vi(10, INT_MAX));
vi dpmin(n + 1, INT_MAX);
dpmin[n] = 0;
for (int i = n - 1, l; i >= 0; --i)
{
l = next_loc[i]['e' - 'a']; // idx of next 'e'
for (int c = 0, k; c < 10; ++c)
{
k = next_loc[i][c]; // jmp location
if (l == n) // es gibt kein 'e'
dp[i][c] = 0;
if (c == 'e' - 'a' || k == n || l == n) // in diesen Faellen darf oder gibt es nichts zu tun
continue;
if (l > k)
dp[i][c] = 2 + dpmin[k];
else
{
if (dpmin[k] == 0)
dp[i][c] = 0;
else
dp[i][c] = 2 + dpmin[k]; // sichere Moeglichkeit: Sprung zu c, dann weiter
for (int c2 = 0; c2 < 10; ++c2) // potentiell besser: sprung direkt ueber c hinaus zu c2
if (next_loc[l + 1][c2] < n && next_loc[l + 1][c2] > k)
dp[i][c] = min(dp[i][c], dp[k][c2]);
dp[i][c] += 2 + (k - l); // arbeit um das erste e zu kommen (eigentlich der erste Schritt)
}
}
dpmin[i] = *min_element(all(dp[i]));
}
cout << dpmin[0] + cntE << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
320 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
316 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
320 KB |
Output is correct |
| 14 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 15 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 16 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
320 KB |
Output is correct |
| 19 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 20 |
Correct |
1 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
324 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
0 ms |
320 KB |
Output is correct |
| 24 |
Correct |
0 ms |
340 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
340 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 30 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 31 |
Correct |
1 ms |
316 KB |
Output is correct |
| 32 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 33 |
Correct |
1 ms |
324 KB |
Output is correct |
| 34 |
Correct |
1 ms |
340 KB |
Output is correct |
| 35 |
Correct |
1 ms |
320 KB |
Output is correct |
| 36 |
Correct |
1 ms |
320 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
960 KB |
Output isn't correct |
| 2 |
Correct |
3 ms |
980 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
700 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
980 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
968 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
960 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
980 KB |
Output isn't correct |
| 9 |
Correct |
3 ms |
960 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
20 ms |
9172 KB |
Output isn't correct |
| 2 |
Incorrect |
19 ms |
8916 KB |
Output isn't correct |
| 3 |
Incorrect |
21 ms |
9172 KB |
Output isn't correct |
| 4 |
Incorrect |
21 ms |
10568 KB |
Output isn't correct |
| 5 |
Incorrect |
24 ms |
10512 KB |
Output isn't correct |
| 6 |
Incorrect |
30 ms |
9340 KB |
Output isn't correct |
| 7 |
Incorrect |
25 ms |
9680 KB |
Output isn't correct |
| 8 |
Incorrect |
22 ms |
9812 KB |
Output isn't correct |
| 9 |
Incorrect |
25 ms |
9684 KB |
Output isn't correct |
| 10 |
Incorrect |
26 ms |
9812 KB |
Output isn't correct |
| 11 |
Incorrect |
21 ms |
10508 KB |
Output isn't correct |
| 12 |
Incorrect |
24 ms |
10452 KB |
Output isn't correct |
| 13 |
Incorrect |
25 ms |
10276 KB |
Output isn't correct |
| 14 |
Incorrect |
24 ms |
10300 KB |
Output isn't correct |
| 15 |
Incorrect |
32 ms |
10452 KB |
Output isn't correct |
| 16 |
Incorrect |
16 ms |
9044 KB |
Output isn't correct |
| 17 |
Incorrect |
21 ms |
9208 KB |
Output isn't correct |
| 18 |
Incorrect |
21 ms |
9212 KB |
Output isn't correct |
| 19 |
Incorrect |
23 ms |
9040 KB |
Output isn't correct |
| 20 |
Incorrect |
26 ms |
9112 KB |
Output isn't correct |
