hdu 1243 反恐训练营

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int dp[2048][2048];
int main()
{
    int i,j,n,s[500],t;
    char s1[2048],s2[2048],s3[2048];
    while(~scanf("%d",&n))
    {
        scanf("%s",s3);
        for(i=0;i<n;i++)
        {
            scanf("%d",&t);
            s[s3[i]-'a']=t;
        }
        scanf("%s %s",s1,s2);
        int len1=strlen(s1);
        int len2=strlen(s2);
        int len=max(len1,len2);
        for(i=0;i<len;i++)
        {
            dp[0][i]=0;
            dp[i][0]=0;
        }
        for(i=0;i<len1;i++)
        {
            for(j=0;j<len2;j++)
            {

                if(s1[i]==s2[j])
                {
                    dp[i+1][j+1]=dp[i][j]+s[s1[i]-'a'];
                }
                else
                {
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
                }
            }
        }
        printf("%d
",dp[len1][len2]);
    }
    return 0;
}