UVA 1625 Color Length （DP）
來源：程序員人生 發布時間：2015-03-28 08:35:50 閱讀次數：2995次
題意：見紫書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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
