제출 #757414

#제출 시각아이디문제언어결과실행 시간메모리
757414drdilyorVim (BOI13_vim)C++17
11.11 / 100
2085 ms524288 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 1e9;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string t;
    cin >> n >> t;
    vector<int> e;
    string s;
    for (char c : t) {
        if (c != 'e') {
            s += c;
            e.push_back(0);
        } else {
            e.back()++;
        }
    }
    n = s.size();

    auto sum =[&](int l, int r) {
        ll s = 0;
        for (;l <= r; l++)
            s += e[l];
        return s;
    };
    vector memo(n, vector(n, -1));
    auto dp = [&](auto& dp, int i, int ne)->int {
        if (ne == n) return 0;
        int& res = memo[i][ne];
        if (res!=-1) return res;
        res = inf;
        set<char> seen;
        for (int j = i+1; j < n; j++) {
            if (seen.count(s[j])) continue;
            seen.insert(s[j]);
            int nne = j;
            while (nne < n && e[nne] == 0) nne++;
            int dist = j - ne;
            int ec = sum(ne, j-1);
            res = min(res, dp(dp, ne, nne) + max(0, dist) + max(0, ec * 2 - 1) + 2);
        }
        //cout << i << ' ' << ne << ' ' << res << '\n';
        return res;
    };

    int ne = 0;
    while (ne < n && e[ne] == 0) ne++;
    cout << dp(dp, 0, ne) << '\n';
    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...