C. An impassioned circulation of affection DP

http://codeforces.com/contest/814/problem/C

12
ooyomioomioo
2
1 o
2 o

这题我是用dp解的，不过好像很慢，比赛的时候算了下不会mle，就没滚动数组了。

dp[i][k][ch]表示以第i位结尾，允许变化k次，所求的字符是ch时的最大连续数量。

如果k > 0，那么dp[i][k][ch] > 0的，因为肯定可以把第i位变了。

那么对于第i位来说，如果str[i]和ch相同，那么应该是dp[i][k][ch] = dp[i - 1][k][ch] + 1，就是和上一段可以结合。而且不用花费变化次数，如果不同，那么需要把str[i]变成ch，才能和前面那一段结合，就是dp[i][k][ch] = dp[i - 1][k - 1][ch] + 1

复杂度n^2 * 26

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
char str[2222];
int lenstr;
//void dfs(char ch, int cur, int nowLen, int did, bool can) {
//    if (did > lenstr) return;
//    dp[ch][did] = max(dp[ch][did], nowLen);
//    if (dp[ch][did] > nowLen && nowLen && can) return;
//    if (cur > lenstr) return;
//    if (str[cur] == ch) {
//        dfs(ch, cur + 1, nowLen + 1, did, false);
//    } else {
//        dfs(ch, cur + 1, 0, did, false);
//        dfs(ch, cur + 1, nowLen + 1, did + 1, true);
//
//    }
//}
int dp[1500 + 2][1500 + 2][26 + 1];
int ans[1500 + 2][26 + 1];
void work() {
    int n;
    scanf("%d", &n);
    scanf("%s", str + 1);
    lenstr = strlen(str + 1);
    for (int ch = 0; ch < 26; ++ch) {
        char cmp = ch + 'a';
        for (int i = 1; i <= lenstr; ++i) {
            for (int k = 0; k <= lenstr; ++k) {
                if (cmp == str[i]) {
                    dp[i][k][ch] = dp[i - 1][k][ch] + 1;
                } else if (k) dp[i][k][ch] = dp[i - 1][k - 1][ch] + 1;
            }
        }
        for (int k = 1; k <= lenstr; ++k) {
            int mx = 0;
            for (int i = 1; i <= lenstr; ++i) {
                mx = max(mx, dp[i][k][ch]);
            }
            ans[k][ch] = mx;
        }
    }
//    cout << dp[2][0]['o' - 'a'] << endl;
//    cout << dp[3][1]['o' - 'a'] << endl;
//    cout << dp[4][1]['o' - 'a'] << endl;
    int q;
    scanf("%d", &q);
    while (q--) {
        char s[22];
        int m;
        scanf("%d%s", &m, s);
        printf("%d\n", ans[m][s[0] - 'a']);
    }

}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}

View Code

C. An impassioned circulation of affection DP

推荐阅读