hdu1243（最长公共子序列变形）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1243

分析：dp[i][j]表示前i个子弹去炸前j个*得到的最大分。其实就是最长公共子序列加每个字母值为1，这里每个字母代表的值变化了一下。

状态转移方程：if(s1[i-1]==s2[j-1])dp[nxt][j]=dp[cur][j-1]+val[s1[i-1]];
                              else  dp[nxt][j]=max(dp[nxt][j-1],dp[cur][j]);

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 1000000007
#define inf 0x3f3f3f3f
#define N 10010
using namespace std;
char s1[],s2[],str[];
int dp[][],val[];
int main()
{
    int n;
    while(scanf("%d",&n)>)
    {
        scanf("%s",str);
        memset(val,,sizeof(val));
        for(int i=;i<=n;i++)scanf("%d",&val[str[i-]]);
        scanf("%s%s",s1,s2);
        int len1=strlen(s1);
        int len2=strlen(s2);
        memset(dp,,sizeof(dp));
        int cur=,nxt=;
        for(int i=;i<=len1;i++)
        {
            for(int j=;j<=len2;j++)
            {
                if(s1[i-]==s2[j-])
                {
                    dp[nxt][j]=dp[cur][j-]+val[s1[i-]];
                }
                else
                dp[nxt][j]=max(dp[nxt][j-],dp[cur][j]);
            }
            swap(cur,nxt);
        }
        printf("%d\n",dp[cur][len2]);
    }
}