HDU-1503 Advanced Fruits(LCS)
题意：
给两个字符串，让你寻找一个最短的字符串，满足其子序列能够构成这两个字符串。
思路：
简单lcs，求出最长公共子序列之后，将两个串构造在一起即可。
代码：
#include <bits/stdc++.h>
using namespace std;
char s1[105], s2[105];
int len1, len2;
string ans, tmp;
int dp[105][105];
bool col[2][105];
void lcs()
{
memset(dp, 0, sizeof dp);
memset(col, 0, sizeof col);
for(int i = 1; i <= len1; ++i)
for(int j = 1; j <= len2; ++j)
{
if(s1[i] == s2[j])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
int x = len1, y = len2;
while(x && y)
{
if(s1[x] == s2[y])
{
col[0][x] = 1;
col[1][y] = 1;
--x, --y;
}
else if(dp[x-1][y] > dp[x][y-1])
--x;
else
--y;
}
}
int main()
{
while(cin >> s1+1 && cin >> s2+1)
{
len1 = strlen(s1+1);
len2 = strlen(s2+1);
lcs();
ans = "";
int x = 1, y = 1;
while(1)
{
tmp = "";
while(x <= len1 && !col[0][x])
tmp += s1[x++];
ans += tmp;
tmp = "";
while(y <= len2 && !col[1][y])
tmp += s2[y++];
ans += tmp;
if(x > len1 && y > len2) break;
ans += s1[x];
++x, ++y;
}
cout << ans << endl;
}
return 0;
}
继续加油~