专栏首页ACM算法日常DP专题 5 | 颜色的长度 - UVA1625(线性DP)

DP专题 5 | 颜色的长度 - UVA1625(线性DP)

题目链接 https://cn.vjudge.net/problem/UVA-1625

【题意】

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

你的任务是找到一种最合理的合并方式,使得新序列的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)对应的新串中“已经出现但还没结束”的字符个数。

状态 新串 第一个串 第二个串

那这个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<bits/stdc++.h>
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<f[1][ch]) ++c[i][j];//判断s[0][i]是不是在新串中第一次出现 
                if(i==g[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<f[0][ch]) ++c[i][j];
                if(j==g[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<bits/stdc++.h>
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<f[1][ch]) ++c[now][j];
                if(i==g[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<f[0][ch]) ++c[now][j];
                if(j==g[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;
}

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:SingleK

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 周赛题解 213

    因为 arr 和 pieces 中都不包含重复的数字,所以直接在pieces中暴力寻找 arr[i] 即可,然后连续的元素是否相同即可。

    ACM算法日常
  • #627 DIV3 题解

    在找到两个数相等之后,由于是子序列可以不连续,在两个数之间随便找一个数即可,所以条件就是且$i+1

    ACM算法日常
  • DP专题 | LIS POJ - 2533

    A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence o...

    ACM算法日常
  • 几道暑期实习笔试题

    DFS 回溯法,先判断组成三连对和组成顺子需要的次数,递归深度 k 就是次数。对于对子和单张的可以直接通过枚举数需要打多少次。可以在组成三连对和顺子的时候增加剪...

    echobingo
  • UESTC 30 &&HDU 2544最短路【Floyd求解裸题】

    最短路 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

    Angel_Kitty
  • [HAOI2012]音量调节 状态型dp

    能达到音量赋值1,否则为0,每一种音量可以达到也可以不达到,调高表示取这件物品,调低表示不取 。

    用户2965768
  • Dynamic Programming - 279. Perfect Squares

    Given a positive integer n, find the least number of perfect square numbers (for...

    用户5705150
  • LeetCode 72. Edit Distance

    ShenduCC
  • 三角形最小路径和

    相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

    你的益达
  • LeetCode 188. Best Time to Buy and Sell Stock IV (动态规划)

    题意:给你一个数组代表每天的股价。你有k次买入和卖出的机会,问你最多能赚多少钱。买入之前必须卖出已有股份。同一天是可以先买,再卖,或者先卖再买的。

    ShenduCC

扫码关注云+社区

领取腾讯云代金券