提出 #76653491

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 3e5 + 5;
int dp[N][3][12];

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt;
    cin >> tt;
    while(tt--)
    {
        string s;
        cin >> s;
        int n = s.size(), k;
        cin >> k;
        for(int i = 0; i < n; i++)
            for(int x = 0; x < 3; x++)
                for(int j = 0; j < 12; j++)
                    dp[i][x][j] = N;
        dp[1][0][0] = 0;
        dp[1][1][0] = (s[1] != 'A');
        dp[1][2][0] = (s[0] != 'A') + (s[1] != 'B');
        for(int i = 1; i + 1 < n; i++)
        {
            for(int j = 0; j <= k; j++)
            {
                dp[i + 1][0][j] = min(dp[i + 1][0][j], min({dp[i][0][j], dp[i][1][j], dp[i][2][j]}));
                if(s[i + 1] == 'A')
                    dp[i + 1][1][j] = min(dp[i + 1][1][j], min({dp[i][0][j], dp[i][1][j], dp[i][2][j]}));
                if(s[i + 1] == 'B')
                    dp[i + 1][2][j] = min(dp[i + 1][2][j], dp[i][1][j]);
                if(s[i + 1] == 'C')
                    dp[i + 1][0][j + 1] = min(dp[i + 1][0][j + 1], dp[i][2][j]);
                dp[i + 1][1][j] = min(dp[i + 1][1][j], min({dp[i][0][j], dp[i][1][j], dp[i][2][j]}) + 1);
                dp[i + 1][2][j] = min(dp[i + 1][2][j], dp[i][1][j] + 1);
                dp[i + 1][0][j + 1] = min(dp[i + 1][0][j + 1], dp[i][2][j] + 1);
            }
            if(s[i - 1] == 'A' && s[i] == 'B' && s[i + 1] == 'C')
            {
                for(int x = 0; x < 3; x++)
                {
                    for(int j = 0; j <= k; j++)
                        dp[i + 1][x][j] = dp[i + 1][x][j + 1];
                }
            }
        }
        int ans = min({dp[n - 1][0][k], dp[n - 1][1][k], dp[n - 1][2][k]});
        if(ans > n)
            ans = -1;
        cout << ans << '\n';
    }
    return 0;
}

提出情報

ジャッジ結果