HDU 2476 String painter

题意：给你一个由小写字母组成的串S，让你变成由小写字母组成的串F，你可以每次将一个区间变成任意一个小写字母，后来的操作可以覆盖原来的区间，求最小操作次数。

|S|<=200

本题与bzoj1260很相似，bzoj1260是给你一个空白串让变成F，本题是在S上修改

bzoj1260的做法：

dp[i][j]表示从i到j涂成F[i~j]的最小花费次数

初始化 dp[i][i]=1

if(F[i]==F[j])
dp[i][j]=min(dp[i+1][j],dp[i][j-1])

表示如果i和j颜色一样，涂i或j的时候把另一个一起涂了就可以了

dp[i][j]=min(dp[i][j],dp[i][k]+[k+1][j])

这个就是普通枚举

HDU这道题是在原串上修改，那么代价应该是小于等于在空白上添加的，开始时总想用一个状态表示，但始终没有办法。看题解原来是做两次DP。一次就如bzoj上的，后一次是

F[i]表示到i为止需要的代价

if(F[i]==S[i]) F[i]=F[i-1]
F[i]=min(F[i],F[j]+dp[j+1][i]) 0<=j<i

CODE:

#include<bits/stdc++.h>
char goal[110],now[110];
int dp[110][110],f[110];
int main(){
    while(scanf(" %s %s",now+1,goal+1)!=EOF){
        memset(dp,0,sizeof(dp));
        memset(f,0,sizeof(f));
        int len=strlen(goal+1);
        for(int i=1;i<=len;++i) dp[i][i]=1;
        for(int i=2;i<=len;++i){
            for(int l=1,r=l+i-1;r<=len;++l,r=l+i-1){
                dp[l][r]=0x3f3f3f3f;
                if(goal[l]==goal[r]){
                    dp[l][r]=std::min(0x3f3f3f3f,std::min(dp[l+1][r],dp[l][r-1]));
                }
                else{
                    for(int mid=l;mid<=r;++mid){
                        dp[l][r]=std::min(dp[l][r],dp[l][mid]+dp[mid+1][r]);
                    }
                }
            }
        }
        f[1]=now[1]==goal[1]?0:1; 
        for(int i=2;i<=len;++i){
            f[i]=0x3f3f3f3f;
            if(now[i]==goal[i]){
                f[i]=f[i-1];
            }
            else
                for(int j=0;j<=i-1;++j){
                    f[i]=std::min(f[i],f[j]+dp[j+1][i]);    
                }
        }
        printf("%d\n",f[len]);
    }
}