【最长公共子序列】hdu 1243 反恐训练营

最长公共子序列：

　　dp[i][j] ：当前子弹的最大得分，

if ([i-1]==[j-1])
　　dp[i][j]=dp[i-1][j-1]+score[a[i-1]];
else
　　dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int MAXN=2000+5;
 5 
 6 char t[MAXN],a[MAXN],b[MAXN];
 7 int dp[MAXN][MAXN];
 8 int score[MAXN];
 9 int n,temp;
10 
11 int max(int x,int y){
12    if(x>y)return x;
13    return y;
14 }
15 
16 int main()
17 {
18     while(scanf("%d",&n)!=EOF){
19         scanf("%s",t);
20         for(int i=0;i<n;i++){
21             scanf("%d",&temp);
22             score[ t[i] ]= temp;
23         }
24         scanf("%s",a);
25         scanf("%s",b);
26 
27         
28         int len1=strlen(a);
29         int len2=strlen(b);
30 
31         memset(dp,0,sizeof dp);
32 
33         for(int i=1;i<=len1;i++){
34             for(int j=1;j<=len2;j++){
35                 if (a[i-1]==b[j-1])
36                     dp[i][j]=dp[i-1][j-1]+score[a[i-1]]; 
37                 else 
38                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
39             }
40         }
41         printf("%d
",dp[len1][len2] );
42     }
43 }