Submission #242932

#TimeUsernameProblemLanguageResultExecution timeMemory
242932BruteforcemanVim (BOI13_vim)C++11
42.50 / 100
40 ms2296 KiB
#include <bits/stdc++.h> using namespace std; const int inf = 1e8; const int maxn = 5005; // 7e4 + 10; const int alpha = 10; string s; int n; int nxt[alpha][maxn]; int opt[maxn]; map <pair <int, int>, int> mem; int cnt[maxn]; int dp(int now, int done) { int jump = opt[done]; if(jump == n) return 0; if(mem.find(make_pair(now, done)) != mem.end()) { return mem[make_pair(now, done)]; } int ans = inf; for(int i = 0; i < alpha; i++) { if(i != 'e' - 'a' && nxt[i][now] < n) { int idx = nxt[i][now]; if(idx < jump) { ans = min(ans, 2 + dp(idx, max(done, idx))); } else { ans = min(ans, 2 + dp(jump, idx) + cnt[idx] - cnt[jump]); } } } return mem[make_pair(now, done)] = ans; } int main() { cin >> n >> s; vector <int> aux (alpha, n); for(int i = n - 1; i >= 0; i--) { for(int j = 0; j < alpha; j++) { nxt[j][i] = aux[j]; } aux[s[i] - 'a'] = i; } int var = n; for(int i = n - 1; i >= 0; i--) { opt[i] = var; if(i > 0 && s[i - 1] == 'e' && s[i] != 'e') { var = i; } } int total = 0; for(int i = 0; i < n; i++) { total += (s[i] != 'e'); cnt[i] = total; } int ans = 2 * count(s.begin(), s.end(), 'e'); cout << ans + dp(0, 0) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...