제출 #41066

#제출 시각아이디문제언어결과실행 시간메모리
41066livaceVim (BOI13_vim)C++14
39.50 / 100
51 ms9324 KiB
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,unroll-all-loops") // #pragma GCC option("arch=native","tune=native") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx") #include <bits/stdc++.h> using namespace std; #define f(_i, _n) for (auto _i = 0; _i < _n; _i++) #define F(_i, _k, _n) for (auto _i = _k; _i < _n; _i++) #define re return #define pb push_back #define all(_v) _v.begin(), _v.end() #define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } #define fi first #define se second typedef pair<int,int> pii; typedef long long ll; typedef long double ld; int nxt[100500][15]; int dp[100500][15]; int cnt_e; int tmp_nxt[10]; int next_not_e[100500]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; string s; cin >> s; n = (int)s.size(); f(i, n) { s[i] -= 'a'; if (s[i] == 4) { cnt_e++; } } f(i, 10) { tmp_nxt[i] = -1; } for (int i = n - 1; i >= 0; i--) { next_not_e[i] = 1e9; f(j, 10) { nxt[i][j] = tmp_nxt[j]; if (tmp_nxt[j] != -1) { next_not_e[i] = min(next_not_e[i], tmp_nxt[j]); } } tmp_nxt[(int)s[i]] = i; } f(i, n + 1) { f(j, 11) { if (j == 4) { continue; } dp[i][j] = 1e9; } } dp[0][10] = 0; int ans = 1e9; f(i, n) { f(j, 11) { if (j == 4) { continue; } // cerr << i << ' ' << j << ' ' << dp[i][j] << '\n'; int nxt_e; if (j == 10) { nxt_e = nxt[i][4]; } else { nxt_e = nxt[nxt[i][j]][4]; } if (nxt_e == -1) { ans = min(ans, dp[i][j]); continue; } f(k, 10) { if (k == 4) { continue; } int pos = nxt[i][k]; if (pos == -1) { continue; } if (nxt_e > pos) { dp[pos][10] = min(dp[pos][10], dp[i][j] + 2); } else { if (pos == next_not_e[nxt_e]) { dp[next_not_e[nxt_e]][10] = min(dp[next_not_e[nxt_e]][10], dp[i][j] + 2 + pos - nxt_e); } else { dp[next_not_e[nxt_e]][k] = min(dp[next_not_e[nxt_e]][k], dp[i][j] + 2 + pos - nxt_e); } } } } } cout << ans + cnt_e; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...