题目链接

【题意】

输入两个长度分别为n和m的颜色序列（n，m<=5000），要求按一定规则合并成一个序列，规则是每次可以把一个序列开头的颜色放到新序列的尾部。例如对于序列GBBY和YRRGB，它们可以合成很多中结果，其中包含这样两种结果，GBYBRYRGB和YRRGGBBYB，对于每个颜色c来说，其跨度L(c)等于新序列中颜色c出现的最大位置和最小位置之差，比如对于上面的两种结果，每个颜色的L(c)和相应的总和如下表所示

颜色	G	Y	B	R	SUM
GBYBRYRGB	7	3	7	2	19
YRRGGBBYB	1	7	3	1	12

你的任务是找到一种最合理的合并方式，使得新序列的L(c)总和最小

【思路】

       紫书276页的一道例题，一开始连状态转移怎么转都想不出来，看了紫书的讲解也也很晕，最后是看了好多别人的题解之后才弄明白的。首先dp的状态就是书上所讲，但我的求解顺序和书上是反过来的，dp(i,j)表示的是从第一个序列头部取走i个元素，第二个序列头部取走j个元素的状态下当前的花费值，所以最后的答案就是dp(n,m). 不难想到dp(i,j)的状态一定是从dp(i-1,j)和dp(i,j-1)的状态转移而来的，所以状态转移方程就一定是这样一个类似于LCS问题的式子

       dp(i,j) = min {dp(i-1,j), dp(i,j-1)} + x

       那这个x是个什么，按照书上所说，每次状态转移的时候，都要把所有的“已经出现但还没结束”的颜色的L(c)值加1，所以在dp(i-1,j)向dp(i,j)的转移过程中，这个x就应该是第一个字符串的前i-1个字符和第二个字符串的前j个字符中所有“已经出现但还没结束”的字符个数，同理在dp(i,j-1)向dp(i,j)的转移过程中，这个x就应该是第一个字符串的前i个字符和第二个字符串的前j-1个字符中所有“已经出现但还没结束”的字符个数

       结合下面的表格，比如两个原始序列为题目描述中的GBBY和YRRGB，现在的状态是dp(1,3)也就是从第一个字符串中取出G，第二个字符串中取出YRR，假设新序列是YRRG，现在要向着dp(1,4)做状态转移，也就是要再从第二个字符串中把G取出来，这时字母Y的头上要加1，G的头上要加1，R不用管因为R已经全部结束了，两个字符串中已经没有R了。所以现在的状态转移x的值为2，也就是dp(1,3)对应的新串中“已经出现但还没结束”的字符个数。

状态	新串	第一个串	第二个串
dp(1,3)	YRRG	BBY	GB
dp(1,4)	YRRGG	BBY	B

       那这个x的值到底怎么求呢，这就需要依赖于dp前的预处理了，用两个数组f[2][26]和g[2][26]分别记录每个字母在每个字符串中第一次出现的位置，最后一次出现的位置，有了这样两个数组，在dp过程中，另开一个c数组，c[i][j]记录当前(i,j)状态下的新串中“已经出现但还没结束”的字符个数，那么最终的状态转移方程就是dp(i,j) = min {dp(i-1,j)+c[i-1][j],dp(i,j-1)+c[i][j-1]} 在dp过程进行的时候借助于f和g不断更新c数组即可，注意数组c的结果也是递推计算得到的。

#include
    
     using namespace std;const int inf=2e9;const int maxn=5050;char s[2][maxn];int len[2];int f[2][26],g[2][26];//记录每个字母在每个字符串中的第一次和最后一次出现位置 int dp[maxn][maxn],c[maxn][maxn];//c[i][j]记录当前状态下新串中出现过但还没结束的字符的个数 void init(){
   //预处理     //初始化     for(int k=0;k<2;++k){        for(int ch=0;ch<26;++ch){            f[k][ch]=inf;            g[k][ch]=-1;        }    }    for(int k=0;k<2;++k){
   //处理每个字符串         for(int ch=0;ch<26;++ch){
   //处理每个字母             for(int i=1;i<=len[k];++i){
   //记录第一次出现的位置                 if(ch+'A'==s[k][i]){                    f[k][ch]=i;                    break;                }            }            for(int i=len[k];i>=1;--i){
   //记录最后一次出现的位置                 if(ch+'A'==s[k][i]){                    g[k][ch]=i;                    break;                }            }        }    }}void solve(){    dp[0][0]=0;    c[0][0]=0;    for(int i=0;i<=len[0];++i){        for(int j=0;j<=len[1];++j){            if(0==i && 0==j) continue;            //计算当前状态dp[i][j]，一定由dp[i-1][j]和dp[i][j-1]转移而来             dp[i][j]=inf;            if(i>0) {
   //由dp[i-1][j]转移而来，取出的是s[0][i]                 dp[i][j]=min(dp[i][j],dp[i-1][j]+c[i-1][j]);                c[i][j]=c[i-1][j];                int ch=s[0][i]-'A';                if(i==f[0][ch] && j
     
      =g[1][ch]) --c[i][j];//判断s[0][i]是不是在新串中最后一次出现             }            if(j>0) {
   //由dp[i][j-1]转移而来，取出的是s[1][j]                 dp[i][j]=min(dp[i][j],dp[i][j-1]+c[i][j-1]);                c[i][j]=c[i][j-1];                int ch=s[1][j]-'A';                if(j==f[1][ch] && i
      
       =g[0][ch]) --c[i][j];            }        }    }    printf("%d\n",dp[len[0]][len[1]]);}int main(){    int t;    scanf("%d",&t);    while(t--){        for(int k=0;k<2;++k) {            scanf("%s",1+s[k]);//字符串的下标从1开始便于处理             len[k]=strlen(1+s[k]);        }        init();        solve();    }    return 0;}
      
     
    

拿滚动数组做优化，还可以进一步优化空间复杂度

#include
    
     using namespace std;const int inf=2e9;const int maxn=5050;char s[2][maxn];int len[2];int f[2][26],g[2][26];//记录每个字母在每个字符串中的第一次和最后一次出现位置 int dp[2][maxn],c[2][maxn]; void init(){
   //预处理     //初始化     for(int k=0;k<2;++k){        for(int ch=0;ch<26;++ch){            f[k][ch]=inf;            g[k][ch]=-1;        }    }    for(int k=0;k<2;++k){
   //处理每个字符串         for(int ch=0;ch<26;++ch){
   //处理每个字母             for(int i=1;i<=len[k];++i){
   //记录第一次出现的位置                 if(ch+'A'==s[k][i]){                    f[k][ch]=i;                    break;                }            }            for(int i=len[k];i>=1;--i){
   //记录最后一次出现的位置                 if(ch+'A'==s[k][i]){                    g[k][ch]=i;                    break;                }            }        }    }}void solve(){    dp[0][0]=0;    c[0][0]=0;    for(int i=0;i<=len[0];++i){        for(int j=0;j<=len[1];++j){            if(0==i && 0==j) continue;            //计算当前状态dp[i][j]，存到滚动数组中的dp[i%2][j]的位置             int now=i%2, pre=1-now;            dp[now][j]=inf;            if(i>0) {                dp[now][j]=min(dp[now][j],dp[pre][j]+c[pre][j]);                c[now][j]=c[pre][j];                int ch=s[0][i]-'A';                if(i==f[0][ch] && j
     
      =g[1][ch]) --c[now][j];            }            if(j>0) {                dp[now][j]=min(dp[now][j],dp[now][j-1]+c[now][j-1]);                c[now][j]=c[now][j-1];                int ch=s[1][j]-'A';                if(j==f[1][ch] && i
      
       =g[0][ch]) --c[now][j];            }        }    }    printf("%d\n",dp[len[0]%2][len[1]]);}int main(){    int t;    scanf("%d",&t);    while(t--){        for(int k=0;k<2;++k) {            scanf("%s",1+s[k]);//字符串的下标从1开始便于处理             len[k]=strlen(1+s[k]);        }        init();        solve();    }    return 0;}