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

KIDx的解题报告

?

第一题（比较简单，不详细解）：

HDU 1159 Common Subsequence

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1159

?

题意：求两个串的最长公共子序列

代码中的dp[i][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[i][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[i][j] = dp[i-1][j-1] + 1;                else dp[i][j] = max (dp[i-1][j], dp[i][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[i][j]表示0到i-1跟0到j-1配对的最大价值

?

状态转移：

①dp[i][j]由dp[i-1][j]转移过来，代价是a[i-1]跟'-'匹配

②由dp[i][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[i][j] = -inf;        dp[0][0] = 0;        for (i = 1; i <= la; i++)//一系列的边界初始化            dp[i][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[i][j] = max (dp[i][j],                        max (dp[i-1][j-1]+v[a[i-1]-'A'][b[j-1]-'A'],                        max (dp[i][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

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

?

?