题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2476
题目大意：给你字符串A、B，每次操作可以将一段区间刷成任意字符，问最少需要几次操作可以使得字符串A等于B。
解题思路：
先计算出将空串刷成字符串B的最小操作数，再去计算将A串刷成B串的最小操作数。
设dp[i][j]表示将空串[i,j]刷成跟B串一样的最小操作次数，所以得到状态转移方程：
dp[i][j]=min(dp[i][j]，dp[i][k]+dp[k+1][j])，(i<=k<j)
if(_str[i]==_str[j])
dp[i][j]--;
这里跟LightOJ 1422 写法差不多。
接下来设ans[i]表示将字符串A的[0,i]刷成B的最小操作次数，得到状态转移方程：
ans[i]=min(ans[i],ans[j]+dp[j+1][i])，（0<=j<i）
代码
#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<string>
#define lc(a) (a<<1)
#define rc(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define _for(i,start,end) for(int i=start;i<=end;i++)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long LL;
const int N=5e2+;
const int INF=0x3f3f3f3f;
const double eps=1e-; int ans[N],dp[N][N];
char str[N],_str[N]; int main(){
while(~scanf("%s",str)){
scanf("%s",_str);
int n=strlen(str);
for(int i=;i<n;i++){
dp[i][i]=;
}
//写法跟lightoj 1422 那个换装类似
for(int len=;len<n;len++){
for(int i=;i+len<n;i++){
int j=i+len;
dp[i][j]=dp[i][j-]+;
for(int k=i;k<=j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);
}
if(_str[i]==_str[j])
dp[i][j]--;
}
}
for(int i=;i<n;i++){
ans[i]=dp[][i];
if(str[i]==_str[i]){
if(i==) ans[]=;
else ans[i]=ans[i-];
}
for(int j=;j<i;j++)
ans[i]=min(ans[i],ans[j]+dp[j+][i]);
}
printf("%d\n",ans[n-]);
}
return ;
}