[題解]BZOJ_1260_塗色

簡單的區間dp，結果竟然寫掛了......還掛的很徹底......狗屎

如果區間左右端點相等，那麼不需要在多花一次去刷，對 f [ i+1 ] [ j ]，f [ i ] [ j-1 ]取個min，

然後枚舉斷點k，直接就是左右區間相加，（簡單吧......）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[105];
int f[105][105];
int min(int a,int b){return a<b?a:b;}

int main()
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    for(int i=1;i<=len;i++)
    for(int j=1;j<=len;j++)f[i][j]=0x3f3f3f3f;
    for(int i=1;i<=len;i++)f[i][i]=1;
    
    for(int l=2;l<=len;l++)
    for(int i=1;i<=len-l+1;i++){
        int j=i+l-1;
        if(s[i]==s[j])f[i][j]=min(f[i-1][j],f[i][j-1]);
        for(int k=i;k<=j-1;k++)
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
    }
    printf("%d",f[1][len]);
}