제출 #44249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44249		neutron_byte	Vim (BOI13_vim)	C++17	8.33 / 100	24 ms	3424 KiB

vim

#include <bits/stdc++.h>
#define INF 10000000
using namespace std;

int n;
string s;

int memo[505][505];
int solve(int cur, int deleted) {
    if (deleted >= n - 1) return 0;

    if (memo[cur][deleted] != -1) return memo[cur][deleted];

    if (cur > deleted) {
        int lastE = -1;
        int cntE = 0;
        for (int i = cur - 1; i > deleted; --i) {
            if (s[i] == 'e') {
                lastE = i;
                ++cntE;
            }
        }

        if (lastE == -1) return memo[cur][deleted] = solve(cur, cur);

        deleted = cur;
        while (deleted < n - 1 && s[deleted + 1] != 'e') ++deleted;

        return memo[cur][deleted] = cur - lastE + cntE + solve(lastE, deleted);
    }

    int rs = INF;
    for (char c = 'a'; c <= 'j'; ++c) {
        if (c == 'e') continue;
        int jumpTo = -1;
        for (int i = cur + 1; i < n; ++i) {
            if (s[i] == c) {
                jumpTo = i;
                break;
            }
        }

        if (jumpTo == -1) continue;

        rs = min(rs, 2 + solve(jumpTo, deleted));
    }

    return memo[cur][deleted] = rs;
}

int main() {
    cin >> n >> s;
    fill(memo[0], memo[0] + 505 * 505, -1);
    cout << solve(0, 0) << endl;
    return 0;
}

• Subtask 1: 8.333333333333334 / 50
• Subtask 2: 0 / 10
• Subtask 3: 0 / 40