【DP最大公共子序列】HDU 1159/1080/1503

基德KID.1412

KIDx的解题报告
 
第一题（比较简单，不详细解）：
HDU 1159 Common Subsequence
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1159
 
题意：求两个串的最长公共子序列

代码中的dp[j]表示0到i-1跟0到j-1的最长公共子序列
 
#include <iostream>using namespace std;#define M 5005int dp[M][M];char a[M], b[M];int main(){    int i, j, la, lb;    while (~scanf ("%s%s", a, b))    {        la = strlen (a), lb = strlen (b);        for (i = 0; i < la; i++)//边界初始化            dp[0] = 0;        for (j = 0; j < lb; j++)            dp[0][j] = 0;        for (i = 1; i <= la; i++)        {            for (j = 1; j <= lb; j++)            {//状态转移                if (a[i-1] == b[j-1])                    dp[j] = dp[i-1][j-1] + 1;                else dp[j] = max (dp[i-1][j], dp[j-1]);            }        }        printf ("%d\n", dp[la][lb]);    }    return 0;} 
 
第二题：
HDU 1080 Human Gene Functions
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1080
 
题意：两个字符串，每个字符串中都可以插入'-'，保证最后两串的长度相等，之后让两串对齐，两串相同位置的字母组成的字符匹配有一个值，问这些值的和最大是多少，是第一题的变形
下图为字符匹配所得价值的表

dp[j]表示0到i-1跟0到j-1配对的最大价值
 
状态转移：
①dp[j]由dp[i-1][j]转移过来，代价是a[i-1]跟'-'匹配
②由dp[j-1]转移过来，代价是b[j-1]跟'-'匹配
③由dp[i-1][j-1]转移过来，代价是a[i-1]跟b[j-1]匹配

#include <iostream>#include <algorithm>using namespace std;#define inf 0x3fffffff#define M 105int dp[M][M], v[20][20] = {0};char a[M], b[M]; int main(){    v[0][0] = v[2][2] = v[6][6] = v[19][19] = 5;    v[0][2] = v[2][0] = -1;    v[0][6] = v[6][0] = -2;    v[0][19] = v[19][0] = -1;    v[2][6] = v[6][2] = -3;    v[2][19] = v[19][2] = -2;    v[6][19] = v[19][6] = -2;    v[7][0] = -3;//7表示'-'，0,2,6,19分别表示A,C,G,T    v[7][2] = -4;    v[7][6] = -2;    v[7][19] = -1;    int i, j, la, lb, t;    scanf ("%d", &t);    while (t--)    {        scanf ("%d%s%d%s", &la, a, &lb, b);        for (i = 0; i <= la; i++)            for (j = 0; j <= lb; j++)                dp[j] = -inf;        dp[0][0] = 0;        for (i = 1; i <= la; i++)//一系列的边界初始化            dp[0] = dp[i-1][0] + v[7][a[i-1]-'A'];        for (j = 1; j <= lb; j++)            dp[0][j] = dp[0][j-1] + v[7][b[j-1]-'A'];        for (i = 1; i <= la; i++)        {            for (j = 1; j <= lb; j++)            {//状态转移方程                dp[j] = max (dp[j],                        max (dp[i-1][j-1]+v[a[i-1]-'A'][b[j-1]-'A'],                        max (dp[j-1]+v[7][b[j-1]-'A'],                        dp[i-1][j]+v[7][a[i-1]-'A'])));            }        }        printf ("%d\n", dp[la][lb]);    }    return 0;} 

 第三题：

HDU 1503 Advanced Fruits
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1503
题意：
给你两个单词，然后你要把两个单词拼接成一个新单词，使得新单词的子序列中包含两个单词，并且要使这个新单词最短
基本思路：
求最长公共子序列，令这个序列只输出一次就可以使新单词最短
记录路径：
增加二维数组road记录状态转移路径
road[j] = 0 表示road[j]由road[i-1][j-1]转移过来，即a[i-1]与b[j-1]属于最长公共子序列中的元素，扫描路径时将hash[i-1]赋值为j-1表示a串的i-1匹配b串的j-1【其中hash初始时全为-1】
road[j] = 1 表示road[j]由road[i-1][j]转移过来
road[j] = 2 表示road[j]由road[j-1]转移过来
输出答案：
先设置start变量【表示b串的当前位置】，扫描a串
①当对于a有hash==-1，说明a不是最长公共子序列中的元素，直接输出并且continue;
②否则b串输出从start到hash的值，因为a跟b[hash]匹配嘛，所以输出b[hash]就不用输出a勒，然后start变为hash + 1;


 
 
#include <iostream>using namespace std;#define M 105int dp[M][M], road[M][M], hash[M];char a[M], b[M];int main(){    int i, j, la, lb;    while (~scanf ("%s%s", a, b))    {        la = strlen (a), lb = strlen (b);        for (i = 0; i < la; i++)            dp[0] = 0;        for (j = 0; j < lb; j++)            dp[0][j] = 0;        memset (road, -1, sizeof(road));        for (i = 1; i <= la; i++)        {            for (j = 1; j <= lb; j++)            {                if (a[i-1] == b[j-1])                {                    dp[j] = dp[i-1][j-1] + 1;                    road[j] = 0;                }                else                {                    if (dp[i-1][j] > dp[j-1])                        dp[j] = dp[i-1][j], road[j] = 1;                    else dp[j] = dp[j-1], road[j] = 2;                }            }        }        int k = 0;        memset (hash, -1, sizeof(hash));        i = la, j = lb;        while (road[j] != -1)//扫描最长公共序列路径        {            if (road[j] == 0)            {                i--, j--;                hash = j;            }            if (road[j] == 2)                j--;            if (road[j] == 1)                i--;        }        int start = 0;//b串的还没打印的第一个字母的位置        for (i = 0; i < la; i++)        {            if (hash == -1)//不属于最长公共子序列的元素            {                printf ("%c", a);                continue;            }//a与b[hash]匹配，属于最长公共子序列            for (j = start; j <= hash; j++)                printf ("%c", b[j]);            start = hash + 1;        }        for (j = start; j < lb; j++)            printf ("%c", b[j]);        printf ("\n");    }    return 0;}