UVA 1625 Color Length （DP）
来源：程序员人生 发布时间：2015-03-28 08:35:50 阅读次数：2857次
题意：见紫书P276
思路：（设1个色彩序列为s1，另外一个为s2）要把最优子结构找到是关键，状态就是天然的履行步骤，d（i,j）表示s1移走了i个元素
s2移走了j个元素的状态。下1步只有两个决策，决策后的剩余的问题和原问题1样，这就是最优子结构。所以每次决策时要保证决策的产生的花费+子问题的解到达最优
所以状态方程明显：dp[i][j]=min(dp[i+1][j],dp[i][j+1])+res[i][j]
本题的难点在于求res[i][j]，所以要在之前对字符串做预处理
代码：
//0 KB 22 ms
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 5050
#define inf 0x3f3f3f3f
char s1[N],s2[N];
int col1[26][2],col2[26][2];
int dp[N][N];
void ini(){
memset(col1,⑴,sizeof(col1));
memset(col2,⑴,sizeof(col2));
}
inline int add(int x,int y){
int s=0;
for(int i=0;i<26;i++){
if(col1[i][1]<=x&&col2[i][1]<=y) continue;
if((col1[i][0]>x&&col2[i][0]>y)||(col1[i][0]>x&&col2[i][0]==⑴)||(col2[i][0]>y&&col1[i][0]==⑴)) continue;
s++;
}
return s;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
ini();
scanf("%s%s",s1,s2);
int len1=strlen(s1);
int len2=strlen(s2);
for(int i=0;i<len1;i++){
if(col1[s1[i]-'A'][0]<0){
col1[s1[i]-'A'][0]=i;
col1[s1[i]-'A' ][1]=i;
}
else col1[s1[i]-'A' ][1]=i;
}
for(int i=0;i<len2;i++){
if(col2[s2[i]-'A'][0]<0){
col2[s2[i]-'A' ][0]=i;
col2[s2[i]-'A'][1]=i;
}
else col2[s2[i]-'A' ][1]=i;
}
dp[len1&1][len2]=0;
for(int i=len1;i>=0;i--)
for(int j=len2;j>=0;j--){
if(i==len1&&j==len2) continue;
int t1=inf,t2=inf;
int tmp=add(i⑴,j⑴);
if(i<=len1⑴) t1=dp[(i+1)&1][j]+tmp;
if(j<=len2⑴) t2=dp[i&1][j+1]+tmp;
dp[i&1][j]= min(t1,t2);
}
printf("%d
",dp[0&1][0]);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
