| UVA - 1625 |
白书
很明显f[i][j]表示第一个取到i第二个取到j的代价
问题在于代价的计算，并不知道每种颜色的开始和结束
和模拟赛那道环形DP很想，计算这次转移会给其他的元素带来的代价，也就是转移前已经出现但还没结束的元素都会代价+1
预处理每种颜色在两个序列中出现的位置bg[i][0/1]和ed[i][0/1]，
计算f[i][j]时同时计算w[i][j]为(i,j)这个状态已经出现还没结束的个数
注意bg要先初始化为INF，计算w：
if(bg[c][0]==i&&bg[c][1]>j) w[i][j]++;
if(ed[c][0]==i&&ed[c][1]<=j) w[i][j]--;
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int N=,INF=1e9;
int T,n,m;
char a[N],b[N];
int f[N][N],w[N][N],bg[][],ed[][];
void dp(){
memset(bg,,sizeof(bg));
memset(ed,,sizeof(ed));
for(int i=;i<;i++) bg[i][]=bg[i][]=INF;
for(int i=;i<=n;i++){
int c=a[i]-'A';
if(bg[c][]==INF) bg[c][]=i;
ed[c][]=i;
}
for(int i=;i<=m;i++){
int c=b[i]-'A';
if(bg[c][]==INF) bg[c][]=i;
ed[c][]=i;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
//f[i][j]=min(f[i-1][j]+cal(i-1,j),f[i][j-1]+cal(i,j-1));
//f[i][j]=min(f[i-1][j],f[i][j-1])+cal(i,j);
if(i==&&j==) continue;
int t1=INF,t2=INF;
if(i>) t1=f[i-][j]+w[i-][j];
if(j>) t2=f[i][j-]+w[i][j-];
f[i][j]=min(t1,t2); if(i>){
w[i][j]=w[i-][j];
int c=a[i]-'A';
if(bg[c][]==i&&bg[c][]>j) w[i][j]++;
if(ed[c][]==i&&ed[c][]<=j) w[i][j]--;
}else{
w[i][j]=w[i][j-];
int c=b[j]-'A';
if(bg[c][]==j&&bg[c][]>i) w[i][j]++;
if(ed[c][]==j&&ed[c][]<=i) w[i][j]--;
//if(b[j]=='R') printf("R %d %d %d %d\n",bg[c][1],ed[c][1],i,j);
}
//printf("%d %d %d %d\n",i,j,f[i][j],w[i][j]);
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%s%s",a+,b+);
n=strlen(a+);m=strlen(b+);
dp();
printf("%d\n",f[n][m]);
}
}
白书的标程用了滚动数组，可以借鉴一下
// UVa1625 Color Length
// Rujia Liu
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn = + ;
const int INF = ; char p[maxn], q[maxn]; // starts from position 1
int sp[], sq[], ep[], eq[]; // sp[i] start positions of character i in p
int d[][maxn], c[][maxn]; // 滚动数组 c[i][j]: how many "incomplete" colors in the mixed sequence int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%s%s", p+, q+); int n = strlen(p+);
int m = strlen(q+);
for(int i = ; i <= n; i++) p[i] -= 'A';
for(int i = ; i <= m; i++) q[i] -= 'A'; // calculate s and e
for(int i = ; i < ; i++)
{
sp[i] = sq[i] = INF;
ep[i] = eq[i] = ;
}
for(int i = ; i <= n; i++)
{
sp[p[i]] = min(sp[p[i]], i);
ep[p[i]] = i;
}
for(int i = ; i <= m; i++)
{
sq[q[i]] = min(sq[q[i]], i);
eq[q[i]] = i;
} // dp
int t = ;
memset(c, , sizeof(c));
memset(d, , sizeof(d));
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
if(!i && !j) continue; // calculate d
int v1 = INF, v2 = INF;
//计算d[i][j], d[i][j]由d[i-1][j]或d[i][j-1]添加一个字母得到
if(i) v1 = d[t^][j] + c[t^][j]; // remove from p
if(j) v2 = d[t][j - ] + c[t][j - ]; // remove from q
d[t][j] = min(v1, v2); // calculate c
if(i)
{
c[t][j] = c[t^][j];
if(sp[p[i]] == i && sq[p[i]] > j) c[t][j]++; //出现新的字母
if(ep[p[i]] == i && eq[p[i]] <= j) c[t][j]--; //一个字母已经结束
}
else if(j)
{
c[t][j] = c[t][j - ];
if(sq[q[j]] == j && sp[q[j]] > i) c[t][j]++;
if(eq[q[j]] == j && ep[q[j]] <= i) c[t][j]--;
}
}
t ^= ;
}
printf("%d\n", d[t^][m]);
}
return ;
}