【DP最大公共子序列】HDU 1159/1080/1503_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 【DP最大公共子序列】HDU 1159/1080/1503

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

 2012/3/13 15:33:19  基德KID.1412  程序员俱乐部  我要评论(0)
  • 摘要:KIDx的解题报告第一题(比较简单,不详细解):HDU1159CommonSubsequence题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1159题意:求两个串的最长公共子序列代码中的dp[i][j]表示0到i-1跟0到j-1的最长公共子序列#include<iostream>usingnamespacestd;#defineM5005intdp[M][M];chara[M],b[M];intmain(){inti,j,la,lb
  • 标签:

KIDx的解题报告

?

第一题(比较简单,不详细解):

HDU 1159 Common Subsequence

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

?

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

代码中的dp[i][j]表示0到i-10到j-1的最长公共子序列

?

#include <iostream>
using namespace std;
#define M 5005

int 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-10到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 105

int 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

题意:

给你两个单词,然后你要把两个单词拼接成一个新单词,使得新单词的子序列中包含两个单词,并且要使这个新单词最短

基本思路:

求最长公共子序列,令这个序列只输出一次就可以使新单词最短

记录路径:

增加二维数组road记录状态转移路径

road[i][j] = 0 表示road[i][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[i][j] = 1 表示road[i][j]由road[i-1][j]转移过来

road[i][j] = 2 表示road[i][j]由road[i][j-1]转移过来

输出答案:

先设置start变量【表示b串的当前位置】,扫描a串

①当对于a[i]有hash[i]==-1,说明a[i]不是最长公共子序列中的元素,直接输出并且continue;

②否则b串输出从start到hash[i]的值,因为a[i]跟b[hash[i]]匹配嘛,所以输出b[hash[i]]就不用输出a[i]勒,然后start变为hash[i] + 1;

?

?

#include <iostream>
using namespace std;
#define M 105

int 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;
}

?

?

  • 大小: 2.9 KB
  • 查看图片附件
  • 相关文章
发表评论
用户名: 匿名