学步园

刘汝佳大牛胖胖白书第四道DP基础练习题

这道题WA了三发

还是精神不够集中,都是不该错的小逻辑

要学会找好状态

DP[i][j]:第i组以j字幕结尾时最小的快数,j字母不在的话就标0

然后搜索DP[n]中的所有非零值取最小

以后做DP记得写转移方程,无论它有多简单(虽然对我这个菜鸟来说没有简单题)

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 1100
#define maxn 20000
using namespace std;
char s1[MAX];

int DP[1100][30], temp[30];
int k;
int main()
{
    //freopen("1.txt", "r", stdin);
    int t, dp0, it, ans;
    scanf("%d", &t);
    while(scanf("%d%s", &k, s1 + 1) != EOF)
    {
        dp0 = 0; ans = maxn;
        memset(temp, 0, sizeof(temp));
        memset(DP, 0, sizeof(DP));
        int len = strlen(s1 + 1); int n = len / k;
        for(int i = 1; i <= k; i++) temp[s1[i] - 'a']++;
        for(int i = 0; i <= 25; i++) if(temp[i]) dp0++;
        for(int i = 0; i <= 25; i++) if(temp[i]) DP[1][i] = dp0;
        for(int i = 2; i <= n; i++)
        {
            memset(temp, 0, sizeof(temp)); dp0 = 0;
            for(int j = (i - 1) * k + 1; j <= i * k; j++) temp[s1[j] - 'a']++;
            for(int j = 0; j <= 25; j++) if(temp[j]) {dp0++; it = j;}
            if(dp0 == 1)
            {
                DP[i][it] = maxn;
                for(int j = 0; j <= 25; j++)
                    if(DP[i - 1][j]) DP[i][it] = min(DP[i][it], j == it ? DP[i - 1][j] : DP[i - 1][j] + 1);

                continue;
            }
            else
            {
                for(int j = 0; j <= 25; j++)
                if(temp[j])
                {
                    DP[i][j] = maxn;
                    for(int k = 0; k <= 25; k++)
                    if(DP[i - 1][k] && temp[k] && k != j) DP[i][j] = min(DP[i][j], DP[i - 1][k] + dp0 - 1);
                    else if(DP[i - 1][k]) DP[i][j] = min(DP[i][j], DP[i - 1][k] + dp0);
                }
            }
        }
        for(int i = 0; i <= 25; i++) if(DP[n][i]) ans = min(ans, DP[n][i]);
        printf("%d\n", ans);
    }
}