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 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-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 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;
}
?
?
相关文章
