题目大意：
两个字符串，可以再中间任何插入空格，然后让这两个串匹配，字符与字符之间的匹配有各自的分数，求最大分数
最长公共子序列模型。
dp[i][j]表示当考虑吧串1的第i个字符和串2的第j个字符时，当前的最大分数，当前有3中可能，
1，i与j直接匹配，那么这个状态是由dp[i-1][j-1]转移过来的.
2，i与空格匹配，那么j就要与i-1匹配了,由dp[i-1][j]转移过来。
3，j与空格匹配，那么i就要与j-1匹配了，由dp[i][j-1]转移过来。
dp的初始值，dp[i][0]与dp[0][i]分别表示串1和串2的第i个字符与空格匹配
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll INF=1e9+7; const ll N=200+10; ll dp[N][N];char s1[N],s2[N]; ll mp[N][N]; void inll() { mp[‘A‘][‘A‘]= 5; mp[‘A‘][‘C‘]=-1; mp[‘A‘][‘G‘]=-2; mp[‘A‘][‘T‘]=-1; mp[‘A‘][1] =-3; mp[‘C‘][‘A‘]=-1; mp[‘C‘][‘C‘]= 5; mp[‘C‘][‘G‘]=-3; mp[‘C‘][‘T‘]=-2; mp[‘C‘][1] =-4; mp[‘G‘][‘A‘]=-2; mp[‘G‘][‘C‘]=-3; mp[‘G‘][‘G‘]= 5; mp[‘G‘][‘T‘]=-2; mp[‘G‘][1] =-2; mp[‘T‘][‘A‘]=-1; mp[‘T‘][‘C‘]=-2; mp[‘T‘][‘G‘]=-2; mp[‘T‘][‘T‘]= 5; mp[‘T‘][1] =-1; mp[1][‘A‘]=-3; mp[1][‘C‘]=-4; mp[1][‘G‘]=-2; mp[1][‘T‘]=-1; } void solve() { memset(dp,0,sizeof dp); ll n; ll m; cin>>n; cin>>s1+1; cin>>m; cin>>s2+1; for(ll i=1;i<=n;i++) dp[i][0]=dp[i-1][0]+mp[s1[i]][1]; for(ll i=1;i<=m;i++) dp[0][i]=dp[0][i-1]+mp[1][s2[i]]; for(ll i=1;i<=n;i++) { for(ll j=1;j<=m;j++) { dp[i][j]=max(dp[i-1][j]+mp[s1[i]][1],dp[i][j-1]+mp[1][s2[j]]); dp[i][j]=max(dp[i-1][j-1]+mp[s1[i]][s2[j]],dp[i][j]); } } cout<<dp[n][m]<<endl; } int main() { ios::sync_with_stdio(0); inll(); ll t; cin>>t; while(t--) solve(); return 0; }
杭电1080 J - Human Gene Functions
原文：https://www.cnblogs.com/Accepting/p/12456616.html