UVA - 1625 Color Length[序列DP 代价计算技巧]

UVA - 1625 Color Length

---

白书

很明显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 ;
}