题意:给你一个由小写字母组成的串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]);
}
}
0 条评论