BZOJ1260

传送门：BZOJ1260

傻逼题。

记$f(i,j)表示把区间[i,j]染色最小操作次数，$则转移是

然后就可以Dp辣！！！

代码上的小细节见下。

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int INF=0x3f3f3f3f;

char S[105];
int f[105][105];
bool used[105][105];

int Dp(int l,int r)
{
    if(used[l][r])
        return f[l][r];
    if(S[l]==S[r])
        f[l][r]=min(Dp(l+1,r),Dp(l,r-1));
    else{
        f[l][r]=INF;
        for(int k=l;k<r;k++)
            f[l][r]=min(f[l][r],Dp(l,k)+Dp(k+1,r));
    }
    used[l][r]=true;
    return f[l][r];
}

void Readdata()
{
    scanf("%s",S+1);
}

void First()
{
    int l=strlen(S+1);
    memset(used,false,sizeof(used));
    for(int i=1;i<=l;i++)
        f[i][i]=used[i][i]=1;
}

void Solve()
{
    printf("%d\n",Dp(1,strlen(S+1)));
}

void Close()
{
    fclose(stdin);
    fclose(stdout);
}

int main()
{
    Readdata();
    First();
    Solve();
    Close();
    return 0;
}