HDU 1243

反恐訓練營

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5514????Accepted Submission(s): 1378

?

當今國際反恐形勢很嚴峻，特別是美國“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<iostream> #include<cstdio> #include<cstring> using namespace std; int dp[2005][2005]; char s[30],m[2005],k[2005]; int b[30]; int main() {int n;while(~scanf("%d",&n)){scanf("%s",s);for(int i=0;i<n;i++){scanf("%d",&b[s[i]-'a']);}scanf("%s%s",m,k);int n1=strlen(m);int n2=strlen(k);memset(dp,0,sizeof(int)*(n1+1));for(int i=0;i<=n2;i++)dp[0][i]=0;for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){if(m[i-1]==k[j-1])dp[i][j]=dp[i-1][j-1]+b[m[i-1]-'a'];else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}printf("%d\n",dp[n1][n2]);} }

?

?

總結

以上是生活随笔為你收集整理的HDU 1243 最长公共子序列 动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。