链接:https://vjudge.net/problem/UVA-1437
思路:想了半天也没啥思路,总感觉贪心能错其实不太行,后来知道这是个区间dp的题,虽然对区间dp没太多了解,但是先把本题记录在这里回去慢慢理解吧。首先是对b串进行遍历,先假设总共刷b的长度那么多次,如果中间有两块相等(不管有没有间隔),总的刷次数就可以-1,这样先对b进行预处理,然后我们比对a和b,如果对应位置不等,那么就像等于从空的开始刷成b,就跟预处理所得到的需要的次数一样,如果相等,该位置就可以忽略,那么只用看前后两个子串需要的次数即可,这就是所谓的区间dp(做法是理解了,但是区间dp还是不太理解,慢慢领悟吧)
代码:
#include<bits/stdc++.h>
using namespace std;
string a,b;
const int maxn = 110;
int dp[maxn][maxn];
int ans[maxn];
int main(){
while(cin>>a>>b){
memset(dp,0,sizeof(dp));
memset(ans,0,sizeof(ans));
//预处理b串
for(int j=0;j<a.size();j++){
for(int i=j;i>=0;i--){
dp[i][j] = dp[i+1][j]+1;
for(int k=i+1;k<=j;k++){
if(b[i]==b[k])
dp[i][j] = min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
}
}
}
for(int i=0;i<a.size();i++)
ans[i] = dp[0][i];
for(int i=0;i<a.size();i++){
if(a[i]!=b[i])//不等则为预处理的结果
for(int j=0;j<i;j++)
ans[i] = min(ans[i],ans[j] + dp[j+1][i]);
else ans[i] = ans[i-1];//相等则等于前一个子问题
}
cout<<ans[a.size()-1]<<endl;
}
return 0;
}
网友评论