【DP最大公共子序列】HDU 1159/1080/1503
KIDx的解题报告第一题（比较简单，不详细解）：
HDU 1159 Common Subsequence
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1159
题意：求两个串的最长公共子序列
代码中的dp表示0到i-1跟0到j-1的最长公共子序列
#include <iostream>using namespace std;#define M 5005int dp;char a, b;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; for (j = 0; j < lb; j++) dp = 0; for (i = 1; i <= la; i++) { for (j = 1; j <= lb; j++) {//状态转移 if (a == b) dp = dp + 1; else dp = max (dp, dp); } } printf ("%d\n", dp); } return 0;}
第二题：
HDU 1080 Human Gene Functions
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1080
题意：两个字符串，每个字符串中都可以插入'-'，保证最后两串的长度相等，之后让两串对齐，两串相同位置的字母组成的字符匹配有一个值，问这些值的和最大是多少，是第一题的变形
下图为字符匹配所得价值的表
http://dl.iteye.com/upload/attachment/0064/5755/6dec206f-e7f3-37c2-a7f2-c596c5076788.gif
dp表示0到i-1跟0到j-1配对的最大价值
状态转移：
①dp由dp转移过来，代价是a跟'-'匹配
②由dp转移过来，代价是b跟'-'匹配
③由dp转移过来，代价是a跟b匹配
#include <iostream>#include <algorithm>using namespace std;#define inf 0x3fffffff#define M 105int dp, v = {0};char a, b; int main(){ v = v = v = v = 5; v = v = -1; v = v = -2; v = v = -1; v = v = -3; v = v = -2; v = v = -2; v = -3;//7表示'-'，0,2,6,19分别表示A,C,G,T v = -4; v = -2; v = -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 = -inf; dp = 0; for (i = 1; i <= la; i++)//一系列的边界初始化 dp = dp + v-'A']; for (j = 1; j <= lb; j++) dp = dp + v-'A']; for (i = 1; i <= la; i++) { for (j = 1; j <= lb; j++) {//状态转移方程 dp = max (dp, max (dp+v-'A']-'A'], max (dp+v-'A'], dp+v-'A']))); } } printf ("%d\n", dp); } return 0;}
第三题：
HDU 1503 Advanced Fruits
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1503
题意：
给你两个单词，然后你要把两个单词拼接成一个新单词，使得新单词的子序列中包含两个单词，并且要使这个新单词最短
基本思路：
求最长公共子序列，令这个序列只输出一次就可以使新单词最短
记录路径：
增加二维数组road记录状态转移路径
road = 0 表示road由road转移过来，即a与b属于最长公共子序列中的元素，扫描路径时将hash赋值为j-1表示a串的i-1匹配b串的j-1【其中hash初始时全为-1】
road = 1 表示road由road转移过来
road = 2 表示road由road转移过来
输出答案：
先设置start变量【表示b串的当前位置】，扫描a串
①当对于a有hash==-1，说明a不是最长公共子序列中的元素，直接输出并且continue;
②否则b串输出从start到hash的值，因为a跟b]匹配嘛，所以输出b]就不用输出a勒，然后start变为hash + 1;
#include <iostream>using namespace std;#define M 105int dp, road, hash;char a, b;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; for (j = 0; j < lb; j++) dp = 0; memset (road, -1, sizeof(road)); for (i = 1; i <= la; i++) { for (j = 1; j <= lb; j++) { if (a == b) { dp = dp + 1; road = 0; } else { if (dp > dp) dp = dp, road = 1; else dp = dp, road = 2; } } } int k = 0; memset (hash, -1, sizeof(hash)); i = la, j = lb; while (road != -1)//扫描最长公共序列路径 { if (road == 0) { i--, j--; hash = j; } if (road == 2) j--; if (road == 1) i--; } int start = 0;//b串的还没打印的第一个字母的位置 for (i = 0; i < la; i++) { if (hash == -1)//不属于最长公共子序列的元素 { printf ("%c", a); continue; }//a与b]匹配，属于最长公共子序列 for (j = start; j <= hash; j++) printf ("%c", b); start = hash + 1; } for (j = start; j < lb; j++) printf ("%c", b); printf ("\n"); } return 0;}
页:
[1]