BZOJ 1260: [CQOI2007]涂色paint 区间DP

#include<cstdio>
#include<iostream>
#include<cstring>
#define R register int
using namespace std;
int n,f[110][110];
char s[110];
signed main() {
    scanf("%s",s+1); n=strlen(s+1); memset(f,0x3f,sizeof(f));
    for(R i=1;i<=n;++i) f[i][i]=1;
    for(R l=2;l<=n;++l) for(R i=1,j=l;j<=n;++i,++j) {
        if(s[i]==s[j]) f[i][j]=min(f[i+1][j],f[i][j-1]);
        else for(R k=i;k<j;++k) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
    } printf("%d\n",f[1][n]);
}