HDU 1243 反恐訓練營 （動态規劃求最長公共子序列）

反恐訓練營

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 3040    Accepted Submission(s): 693

Problem Description 當今國際反恐形勢很嚴峻，特别是美國“9.11事件”以後，國際恐怖勢力更是有恃無恐，制造了多起駭人聽聞的恐怖事件。基于此，各國都十分擔心恐怖勢力會對本國社會造成的不穩定，于是紛紛在本國的軍隊、警察隊伍中開展了反恐訓練。作為反恐立場堅定的大國，中國也十分重視在人民解放軍、武裝警察部隊、人民警察隊伍中反恐訓練，還專門成立了反恐特警隊。

炜炜是反恐特警隊的一名新隊員，現在正在接受教育訓練。這幾天剛好是射擊訓練第二階段——實彈應變訓練的日子，此前的第一階段裡，炜炜經過努力，已經将自己訓練成為一個百發百中的神搶手了！這次，他将背着國産最新型12.7mm重型狙擊槍進行訓練比賽。

這次訓練比賽的規則是這樣的：

1、每個隊員從出發點開始，沿着一條唯一的筆直道路跑直到終點，途中不允許往回跑，否則将被取消比賽資格。

2、出發前，每個隊員的槍膛内都被裝了順序一樣的、用小寫英文字母标明類型的子彈序列，每位隊員被告知這一序列的資訊；同時，每位隊員也被告知恐怖分子即将出現的序列和類型（同樣用小寫英文字母标明類型）。

3、在跑動的過程中，若發現“恐怖分子”，特警隊員可以選擇用槍擊斃他，來得到寫在“恐怖分子”胸前的得分，但是前提是他使用的子彈類型必須和“恐怖分子”類型相同，否則，即使擊斃了“恐怖分子”，也得不到分數；當然選擇不擊斃他也是可以的，這樣他不會從那個“恐怖分子”身上得到分數。

4、允許特警隊員放空槍，這樣可以消耗掉型号不對的子彈而不至于殺死“恐怖分子”（當然每個特警隊員都不會愚蠢到不裝消音裝置就放空槍，以至于吓跑“恐怖分子”），等待槍口出現正确型号的子彈擊斃他得分。

這裡，我們假定：

1、對于每個隊員，途中出現恐怖分子的地點、時間、類型也是完全一樣的。

2、每顆子彈都是品質合格的，都可以發揮殺傷效力

3、由于隊員各個都是神槍手，一旦他選擇了正确的子彈，向目标射擊，目标100%被爆頭

4、每個隊員的記憶力超強，能記住所有子彈序列資訊和恐怖分子序列資訊。

5、每個隊員體力足夠好，能跑完全程，并做他想要做的

6、“恐怖分子”是不動的，小範圍内不存在多于一個的恐怖分子；

炜炜需要你的幫助，告訴他如何做，才能得到最高的分數。現在如果告訴你出發時槍膛内子彈的序号和型号、恐怖分子出現的序号和類型，你能告訴炜炜他最多能得到多少分數嗎？

Input 輸入資料的第一行有一個整數N表示子彈和恐怖分子的類型數。随後的一行是各種恐怖分子類型的一行字母，兩個字母之間沒有任何字元。接下來的一行是擊斃上一行對應位置恐怖分子類型的得分數，每個分數之間恰有一個空格。第三第四行分别表示開始時槍膛内子彈的序列（左邊的先打出）和恐怖分子出現的序列（左邊的先出現），字母之間都沒有任何字元。

每個測試資料之間沒有空格和空行。你的程式必須通過全部測試資料，才能被判為AC。

Output 對于每一個測試資料，輸出炜炜最多能得到的分數。

Sample Input

3
abc
1 1 1
abc
ccc
3
abc
1 1 1
ccc
aba
        

Sample Output

1
0
        

還是求最長公共子序列，但是每次遇到相同的字母後，該加上字母對應的分數

#include<stdio.h>
#include<map>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
int N;
int main(int argc, char *argv[])
{
    vector<vector<int> >c;
    map<int,char>m;
    string s,a,b;
    int score;
    while(~scanf("%d",&N))
    {
        cin>>s;
        for(int i=0;i!=s.size();++i)
        {
            scanf("%d",&score);
            m[s[i]]=score;
        }
        cin>>a;
        cin>>b;
        int x=a.size();
        int y=b.size();
        int SIZE=x>y?x:y;
        SIZE+=1;
        c.resize(SIZE);
        for(int i=0;i<c.size();++i)
        {
            c[i].resize(SIZE);
        }
        for(int i=0;i<x;++i)
            c[i][0]=0;
        for(int j=0;j<y;++j)
            c[0][j]=0;
        for(int i=1;i<=x;++i)
            for(int j=1;j<=y;++j)
            {
                if(a[i-1]==b[j-1])
                {
                    c[i][j]=c[i-1][j-1]+m[a[i-1]];
                }
                else if(c[i][j-1]>=c[i-1][j])
                {
                    c[i][j]=c[i][j-1];
                }
                else
                    c[i][j]=c[i-1][j];
            }
        printf("%d\n",c[x][y]);
    }
    return 0;
}