题目

UVa 1625 Color Length

大意^{[1]}

输入两个长度分别为 n 和 m(n, m <= 5000) 的颜色序列,要求按顺序合并成同一个序列,即每次可以把一个序列开头的颜色放到新序列的尾部。

例如,两个颜色系列 GBBY 和 YRRGB,至少有两种合并结果:GBYBRYRGB 和 YRRGGBBYB。对于每个颜色 c 来说,其跨度 L(c) 等于最大位置和最小位置之差。例如,对于上面两种合并结果,每个颜色的 L(c) 和所有 L(c) 的总和如下图所示。

你的任务是找一种合并方式,使得所有 L(c) 的总和最小。

思路^{[1]}

本题属于线性 DP 模型,状态空间为 f[i][j],代表第一个序列[:i]与第二个序列[:j]构成的新序列的总和最小值。

在计算 f[i][j] 时, 可以由 f[i-1][j] 或 f[i][j-1] 递推过来。以 f[i-1][j] 递推到 f[i][j] 为例,此时f[i][j] = f[i-1][j] + c[i-1][j](在 [i-1][j] 区间已经出现但未全部出现的字符的数量)。

为了计算 c 数组,需要计算每一个字符分别在两个原始字符串中出现的开始位置和结束位置。

对于 c 数组的递推过程,详见代码。

代码^{[1]}

// https://www.cnblogs.com/violet-acmer/p/11010582.html
// https://github.com/aoapc-book/aoapc-bac2nd/blob/master/ch9/UVa1625.cpp
// https://onlinejudge.org/external/16/1625.pdf
// UVa 1625
// Tip: 在for里面,每次需要初始化变量 memset!!!
//      memset 耗时,TLE
#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
int d[maxn][maxn], c[maxn][maxn];
char p[maxn], q[maxn];
int n, m;
int sp[26], ep[26], sq[26], eq[26];
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%s%s", p+1, q+1);
        n = strlen(p+1);
        m = strlen(q+1);
        for(int i = 1; i <= n; i++) p[i] -= 'A';
        for(int i = 1; i <= m; i++) q[i] -= 'A';

        for(int i = 0; i < 26; i++) {sp[i] = sq[i] = 0x3f3f3f3f; ep[i] = eq[i] = 0; }
        for (int i=1;i<=n;++i) {
            sp[p[i]] = min(sp[p[i]], i);
            ep[p[i]] = i;
        }
        for (int i=1;i<=m;++i) {
            sq[q[i]] = min(sq[q[i]], i);
            eq[q[i]] = i;
        }
        for (int i=0;i<=n;++i) {
            for (int j=0;j<=m;++j) {
                if (i) {
                    c[i][j] = c[i-1][j];
                    if (sp[p[i]] == i && sq[p[i]] > j) c[i][j]++;
                    if (ep[p[i]] == i && eq[p[i]] <= j) c[i][j]--;
                } else if (j) {
                    c[i][j] = c[i][j-1];
                    if (sq[q[j]] == j && sp[q[j]] > i) c[i][j]++;
                    if (eq[q[j]] == j && ep[q[j]] <= i) c[i][j]--;
                }
            }
        }
        for (int i=0;i<=n;++i) {
            for (int j=0;j<=m;++j) {
                if (!i && !j) continue;
                d[i][j]=0x3f3f3f3f;
                if (i) d[i][j] = min(d[i][j], d[i-1][j] + c[i-1][j]);
                if (j) d[i][j] = min(d[i][j], d[i][j-1] + c[i][j-1]);
                //cout<<"i:"<<i<<" j:"<<j<<" d:"<<d[i][j]<<endl;
            }
        }
        
        printf("%d\n", d[n][m]);
    }
    return 0;
}

参考

[1]. 刘汝佳. 算法竞赛入门经典 第 2 版[M]. 北京:清华大学出版社,2014:276

欢迎分享,引用。若转载,请联系我,谢谢配合。
本文地址:https://qoogle.top/xiaoxu-tutorial-uva-1625-color-length/
0 0 vote
Article Rating
Subscribe
提醒
guest
1 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments

[…] 小旭讲解 UVa 1625. Color Length […]