hdu2476

发表于 | 分类于 | 阅读数 次

链接:hdu2476

题解

  • DP[i][j]表示把a串i~j变为b串的最小变化次数,但是如果a,b中某一对应位相同,可以考虑不变
  • 可以先考虑没有相同的情况然后再处理有相同的情况.ans[j]表示1~j串a变为b的最小变化次数
  • 显然如果a[j]==b[j]ans[j]=min(ans[j],ans[j-1])
  • 否则ans[j]=min(ans[j],ans[i]+dp[i+1][j]) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=107;
const int inf=0x3f3f3f3f;
char str[N],ptr[N];
int dp[N][N],ans[N],n;
int main(){
	while(~scanf("%s%s",str+1,ptr+1)){
		memset(dp,0,sizeof(dp));
		n=strlen(str+1);
		rep(i,1,n)dp[i][i]=1;
		rep(l,2,n)rep(i,1,n-l+1){
			int j=i+l-1;
			dp[i][j]=dp[i+1][j]+1;
			rep(k,i+1,j)if(ptr[i]==ptr[k])dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
		}
		rep(j,1,n){
			ans[j]=dp[1][j];
			if(str[j]==ptr[j])ans[j]=min(ans[j],ans[j-1]);
			else rep(i,1,j-1)ans[j]=min(ans[j],ans[i]+dp[i+1][j]);
		}
		printf("%d\n",ans[n]);
	}
	return 0;
}