题目： http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1305
这个题就是一个类似公共子串的dp，但是加了权值，其实还是很简单。
当匹配时相似程度是5，不匹配是-4，添加空隙是-7。那么dp[i][j]的值就来自于三个方式：
1、在s2[j]后添加空隙，那么相似程度就是dp[i][j-1] - 7
2、在s1[i]后添加空隙，那么相似程度就是dp[i-1][j] - 7
3、直接拿s1[i]和s2[j]匹配，如果匹配相似程度就是dp[i-1][j-1] + 5，如果不匹配相似程度就是dp[i-1][j-1] - 4
最后找一下字典序最小的，就是这样了。。。就是代码写的搓了一点。
#include <stdio.h>
#include <string.h>
#include <algorithm> int dp[][];
char s1[], s2[][]; int main()
{
int t, ans = , x;
scanf("%s %d", s1, &t);
int n = strlen(s1);
for(int item = ; item < t; item++)
{
scanf("%s", s2[item]);
int m = strlen(s2[item]);
dp[][] = ;
for(int i = ; i <= n; i++)
dp[i][] = dp[i-][] - ;
for(int j = ; j <= m; j++)
dp[][j] = dp[][j-] - ;
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
dp[i][j] = std::max(std::max(dp[i-][j] - , dp[i][j-] - ), dp[i-][j-] + (s1[i-] == s2[item][j-] ? : -));
}
}
if(dp[n][m] > ans || (dp[n][m] == ans && strcmp(s2[x], s2[item]) > ))
{
ans = dp[n][m];
x = item;
}
}
printf("%d\n%s\n", ans, s2[x]);
return ;
}