Lcs思想

HDU 1080

类似于Lcs

两个字符串匹配最大子序列时，dp【i-1】【j】状态只考虑s1串到了i-1，s2串到了j时的情况

对于这个题，dp【i-1】【j】的状态要想全部匹配，那么s2串要补空格（s1未匹配完，s2就截止到j的位置，别的不看，那么s2就得补空格！！！

剩下的就好做了

#include <iostream>
#include <cstring>
#include <map>
using namespace std;
const int N=200;
const int inf=0x3f3f3f3f;
int dp[N][N];
char s1[N],s2[N];
map<char,int>mp;
int Map[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,-inf};
void init() {
    mp['A']=0,mp['C']=1,mp['G']=2,mp['T']=3,mp['-']=4;
}
int main() {
    init();
    int t,len1,len2;
    cin>>t;
    while(t--) {
        cin>>len1>>s1+1;
        cin>>len2>>s2+1;
        dp[0][0]=0;
        for(int i=1;i<=len1;i++) dp[i][0]=dp[i-1][0]+Map[mp[s1[i]]][mp['-']];
        for(int i=1;i<=len2;i++) dp[0][i]=dp[0][i-1]+Map[mp['-']][mp[s2[i]]];
        for(int i=1;i<=len1;i++) {
            for(int j=1;j<=len2;j++) {
                dp[i][j]=max(dp[i-1][j-1]+Map[mp[s1[i]]][mp[s2[j]]],
                    max(dp[i-1][j]+Map[mp[s1[i]]][mp['-']],
                    dp[i][j-1]+Map[mp['-']][mp[s2[j]]]));
            }
        }
        cout<<dp[len1][len2]<<endl;
    }
    return 0;
}