HDu 1243対テロ訓練キャンプ(DP+空間最適化)
3414 ワード
テロ対策訓練キャンプ
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2067 Accepted Submission(s): 454
Problem Description
今日の国際テロ対策の情勢はとても厳しくて、特に米国の“9.11事件”の後で、国際テロ勢力は更に頼りにして恐れなくて、多くの恐ろしいテロ事件を作りました.これにより、各国はテロ勢力が自国社会に与える不安定さを懸念し、自国の軍隊や警察隊でテロ対策訓練を行っている.反テロの立場が確固たる大国として、中国も人民解放軍、武装警察部隊、人民警察隊における反テロ訓練を非常に重視し、反テロ特警隊を設立した.
炜炜は反テロ特警隊の新しい隊員で、現在訓練を受けている.ここ数日はちょうど射撃訓練の第2段階である実弾応変訓練の日で、これまでの第1段階では、炜炜は努力を経て、すでに自分を百発百中の神の奪い手に訓練した.今回は、国産最新型の12.7 mm重型狙撃銃を背に練習試合を行う.
今回の訓練試合のルールはこうです.
1、各選手は出発点から、唯一のまっすぐな道に沿ってゴールまで走り、途中で戻ることは許されない.そうしないと、試合の資格が取り消される.
2、出発前、各隊員の銃口には順番が同じで、小文字の英字でタイプの弾丸のシーケンスが記載されており、各隊員はこのシーケンスの情報を知られている.また、テロリストが現れるシーケンスとタイプ(同じように小文字の英字でタイプを表記する)も隊員一人一人に知られている.
3、走る过程の中で、もし"テロリスト"を発见するならば、特警の队员は铳で彼を杀すことを选んで、"テロリスト"の胸の前に书いた得点を得ることができて、しかし前提は彼が使う弾丸のタイプが"テロリスト"のタイプと同じでなければならなくて、さもなくば、たとえ"テロリスト"を杀しても、点数を得ることができません;もちろん彼を殺さないことを選んでもいい.そうすれば、彼はその「テロリスト」から点数を得ることはできない.
4、特警隊員に銃を空にすることを許可し、「テロリスト」を殺すことなく型番の悪い弾丸を消費することができる(もちろん、各特警隊員は消音装置を装着せずに銃を空にするほど愚かではなく、「テロリスト」を脅かすほどだ).銃口に正確な型番の弾丸が現れて彼の得点を射殺するのを待つ.
ここでは、次のように仮定します.
1、隊員一人一人に対して、途中でテロリストが現れた場所、時間、タイプも全く同じです.
2、どの弾も品質が合格し、殺傷力を発揮できる
3、队员はそれぞれ神枪手なので、正确な弾を选び、目标に向かって射撃すると、目标は100%爆発する
4、各隊員の記憶力は超強く、すべての弾丸シーケンス情報とテロリストシーケンス情報を記憶することができる.
5、選手一人一人が体力が十分で、完全な距離を走ることができて、彼がやりたいことをすることができます.
6、「テロリスト」は動かず、小範囲で1人以上のテロリストは存在しない.
炜炜はあなたの助けが必要で、彼にどのようにして、最高の点数を得ることができるかを教えます.今、出発時に銃口内の弾丸の番号と型番、テロリストが現れた番号とタイプを教えてくれれば、彼が最大でどれだけの点数を得ることができるか教えてくれませんか.
Input
入力データの最初の行には、弾丸とテロリストのタイプ数を表す整数Nがある.次の行は様々なテロリストタイプの1行のアルファベットで、2つのアルファベットの間には何の文字もありません.次の行は、前の行の対応する位置テロリストタイプを射殺した点数で、各点数の間にはちょうどスペースがある.3行目の4行目は、開始時に銃口内弾のシーケンス(左の先打ち)とテロリストが現れるシーケンス(左の先現れ)をそれぞれ表し、アルファベットの間には何の文字もありません.
各テストデータの間にスペースと空の行はありません.あなたのプログラムはすべてのテストデータに合格しなければ、ACと判定されません.
Output
各テストデータについて、最も多く得られる点数を出力します.
Sample Input
Sample Output
Author
JGShining
Recommend
Ignatius.L
構想:dp[x][y]は前x個の弾丸を表し、前y個人の最大得点を打つ.
x番目の弾丸がy番目の人に対応する場合.ではdp[x][y]=dp[x-1][y-1]+は彼の点数を打つ.
そうでなければdp[x][y]=max(dp[x][y-1],dp[x-1][y]);
通常2次元空間を開くことは許されないので、最適化の下にスクロール配列、1次元空間が必要です.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2067 Accepted Submission(s): 454
Problem Description
今日の国際テロ対策の情勢はとても厳しくて、特に米国の“9.11事件”の後で、国際テロ勢力は更に頼りにして恐れなくて、多くの恐ろしいテロ事件を作りました.これにより、各国はテロ勢力が自国社会に与える不安定さを懸念し、自国の軍隊や警察隊でテロ対策訓練を行っている.反テロの立場が確固たる大国として、中国も人民解放軍、武装警察部隊、人民警察隊における反テロ訓練を非常に重視し、反テロ特警隊を設立した.
炜炜は反テロ特警隊の新しい隊員で、現在訓練を受けている.ここ数日はちょうど射撃訓練の第2段階である実弾応変訓練の日で、これまでの第1段階では、炜炜は努力を経て、すでに自分を百発百中の神の奪い手に訓練した.今回は、国産最新型の12.7 mm重型狙撃銃を背に練習試合を行う.
今回の訓練試合のルールはこうです.
1、各選手は出発点から、唯一のまっすぐな道に沿ってゴールまで走り、途中で戻ることは許されない.そうしないと、試合の資格が取り消される.
2、出発前、各隊員の銃口には順番が同じで、小文字の英字でタイプの弾丸のシーケンスが記載されており、各隊員はこのシーケンスの情報を知られている.また、テロリストが現れるシーケンスとタイプ(同じように小文字の英字でタイプを表記する)も隊員一人一人に知られている.
3、走る过程の中で、もし"テロリスト"を発见するならば、特警の队员は铳で彼を杀すことを选んで、"テロリスト"の胸の前に书いた得点を得ることができて、しかし前提は彼が使う弾丸のタイプが"テロリスト"のタイプと同じでなければならなくて、さもなくば、たとえ"テロリスト"を杀しても、点数を得ることができません;もちろん彼を殺さないことを選んでもいい.そうすれば、彼はその「テロリスト」から点数を得ることはできない.
4、特警隊員に銃を空にすることを許可し、「テロリスト」を殺すことなく型番の悪い弾丸を消費することができる(もちろん、各特警隊員は消音装置を装着せずに銃を空にするほど愚かではなく、「テロリスト」を脅かすほどだ).銃口に正確な型番の弾丸が現れて彼の得点を射殺するのを待つ.
ここでは、次のように仮定します.
1、隊員一人一人に対して、途中でテロリストが現れた場所、時間、タイプも全く同じです.
2、どの弾も品質が合格し、殺傷力を発揮できる
3、队员はそれぞれ神枪手なので、正确な弾を选び、目标に向かって射撃すると、目标は100%爆発する
4、各隊員の記憶力は超強く、すべての弾丸シーケンス情報とテロリストシーケンス情報を記憶することができる.
5、選手一人一人が体力が十分で、完全な距離を走ることができて、彼がやりたいことをすることができます.
6、「テロリスト」は動かず、小範囲で1人以上のテロリストは存在しない.
炜炜はあなたの助けが必要で、彼にどのようにして、最高の点数を得ることができるかを教えます.今、出発時に銃口内の弾丸の番号と型番、テロリストが現れた番号とタイプを教えてくれれば、彼が最大でどれだけの点数を得ることができるか教えてくれませんか.
Input
入力データの最初の行には、弾丸とテロリストのタイプ数を表す整数Nがある.次の行は様々なテロリストタイプの1行のアルファベットで、2つのアルファベットの間には何の文字もありません.次の行は、前の行の対応する位置テロリストタイプを射殺した点数で、各点数の間にはちょうどスペースがある.3行目の4行目は、開始時に銃口内弾のシーケンス(左の先打ち)とテロリストが現れるシーケンス(左の先現れ)をそれぞれ表し、アルファベットの間には何の文字もありません.
各テストデータの間にスペースと空の行はありません.あなたのプログラムはすべてのテストデータに合格しなければ、ACと判定されません.
Output
各テストデータについて、最も多く得られる点数を出力します.
Sample Input
3
abc
1 1 1
abc
ccc
3
abc
1 1 1
ccc
aba
Sample Output
1
0
Author
JGShining
Recommend
Ignatius.L
構想:dp[x][y]は前x個の弾丸を表し、前y個人の最大得点を打つ.
x番目の弾丸がy番目の人に対応する場合.ではdp[x][y]=dp[x-1][y-1]+は彼の点数を打つ.
そうでなければdp[x][y]=max(dp[x][y-1],dp[x-1][y]);
通常2次元空間を開くことは許されないので、最適化の下にスクロール配列、1次元空間が必要です.
///hdu 1243
#include<iostream>
#include<cstring>
using namespace std;
const int mm=4030;
char s[mm],ss[mm];
int vis[mm],have[mm];
int dp[2][mm];
int m;
int main()
{
while(cin>>m)
{ memset(have,0,sizeof(have));
memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
cin>>s;
for(int i=0;i<m;i++)
cin>>have[s[i]];
cin>>s>>ss;
int s_len=strlen(s);
int ss_len=strlen(ss);
int v;
for(int i=1;i<=s_len;i++)
{ v=i%2;
for(int j=1;j<=ss_len;j++)
{
if(s[i-1]==ss[j-1])
dp[v][j]=dp[v^1][j-1]+have[s[i-1]];
else dp[v][j]=dp[v^1][j]>dp[v][j-1]?dp[v^1][j]:dp[v][j-1];
}
}
cout<<dp[s_len%2][ss_len]<<"
";
}
}