复制上一题总结
caioj 1069到1071 都是最长公共字序列的拓展，我总结出了一个模型，屡试不爽
（１） 字符串下标从1开始，因为０用来表示字符为空的情况，而不是第一个字符
（２）初始化问题。
一般设f[i][j]为第一个字符前ｉ个，第二个字符前ｊ个的最优价值
f[0][0] = 0
然后要初始化f[i][0], f[0][i]
这个时候要根据题意。
这个时候就是一个字符有，一个字符空的情况
（３）然后就可以两层for了
这个时候记住根据题目有不同的决策，取最优
一般有匹配字符和不匹配字符（如加空格）两种情况
按照题目而定
最后要注意如果是取min初值要最大，max初值最小
或者直接用其中一个决策作为初值
依然是套模型
初始化的话显然空字符就是全是'-'
然后依然是匹配字符或者是选'-'
爽！！！！
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112;
char a[MAXN], b[MAXN];
int f[MAXN][MAXN], lena, lenb;int d[5][5] = { 5, -1, -2, -1, -3,-1, 5, -3, -2, -4, -2, -3, 5, -2, -2,-1, -2, -2, 5, -1,-3, -4, -2, -1, 0 };int ID(char x)
{if(x == 'A') return 0;if(x == 'C') return 1;if(x == 'G') return 2;if(x == 'T') return 3;if(x == '-') return 4;
}
int dist(char x, char y) { return d[ID(x)][ID(y)]; }int main()
{scanf("%d%s%d%s", &lena, a + 1, &lenb, b + 1); f[0][0] = 0;REP(i, 1, lena + 1) f[i][0] = f[i-1][0] + dist(a[i], '-');REP(i, 1, lenb + 1) f[0][i] = f[0][i-1] + dist(b[i], '-');REP(i, 1, lena + 1)REP(j, 1, lenb + 1){f[i][j] = f[i-1][j-1] + dist(a[i], b[j]);f[i][j] = max(f[i][j], max(f[i-1][j] + dist(a[i], '-'), f[i][j-1] + dist(b[j], '-')));} printf("%d\n", f[lena][lenb]);return 0;
}