颜色的长度 Color Length

题面翻译

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

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

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

感谢 @Bruce·Darwin·Xu 提供的翻译。

题目描述

PDF

输入格式

输出格式

这道题是一个LCS的变形，设 f[i][j] 1到i，1到j 的最小费用，我们需要计算出 1到i，1到j 下，有哪些颜色已经开始而且尚未结束。可以这么想：有哪些颜色是前缀 1到i，1到j 有 ，后缀 i+1到n，j+1到m也有的，那不就可以求出 有哪些颜色已经开始 还尚未结束的个数吗？方程显然，代码里面都写得很清楚。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define fo(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;
const int N=5e3+5,INF=0x3f3f3f3f;
#define PII pair<int,int>
 
PII p2[N],q2[N];
int g[N][N],f[N][N];
int cnt1(int x){
    int ans=0;
    while(x){
        ans+=(1&x);
        x>>=1;
    }
    return ans;
}
 
void solve(){
    string p,q;
    cin>>p>>q;
    int n=p.size(),m=q.size();
    p='#'+p,q='#'+q;
    //prework
    p2[0]=p2[n+1]={0,0};q2[0]=q2[m+1]={0,0};
    for(int i=1;i<=n;i++)
        p2[i].first=(p2[i-1].first|(1<<(p[i]-'A')));
    for(int i=1;i<=m;i++)
        q2[i].first=(q2[i-1].first|(1<<(q[i]-'A')));
    for(int i=n;i>=1;i--)
        p2[i].second=(p2[i+1].second|(1<<(p[i]-'A')));
    for(int i=m;i>=1;i--)
        q2[i].second=(q2[i+1].second|(1<<(q[i]-'A')));
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++){
            g[i][j]=cnt1((p2[i].first|q2[j].first)&(p2[i+1].second|q2[j+1].second));
        }
    //dp
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++){
            if(!i&&!j) {f[i][j]=0;continue;}
            int &v=f[i][j]; v=INF;
            if(i) v=min(v,f[i-1][j]+g[i-1][j]);
            if(j) v=min(v,f[i][j-1]+g[i][j-1]);
        }
    cout<<f[n][m]<<endl;
}
 
int main(){
    //std::ios::sync_with_stdio(0);cin.tie(0);
    int T;cin>>T;
    while(T--) solve();
}