HDU 1243対テロ訓練キャンプ
3363 ワード
テロ対策訓練キャンプ
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3564 Accepted Submission(s): 840
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
分析:
これは最大の共通サブシーケンス問題であり、最長の共通サブシーケンス問題と類似しており、文字は同じでヒットし、点数はdp[i][j]=dp[i][j]=dp[i-1][j-1]+score[i];
文字の違いは、MAX(dp[i-1][j],dp[i][j-1])という大きな状態を探します.
もう一つの問題は、配列が1005だけでは足りないので、2005を開いてから提出することができます.
コードは次のとおりです.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3564 Accepted Submission(s): 840
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
分析:
これは最大の共通サブシーケンス問題であり、最長の共通サブシーケンス問題と類似しており、文字は同じでヒットし、点数はdp[i][j]=dp[i][j]=dp[i-1][j-1]+score[i];
文字の違いは、MAX(dp[i-1][j],dp[i][j-1])という大きな状態を探します.
もう一つの問題は、配列が1005だけでは足りないので、2005を開いてから提出することができます.
コードは次のとおりです.
#include <stdio.h>
#include <string.h>
int dp[2005][2005];
int max(int a,int b)
{
return a>b? a:b;
}
int main()
{
int n,a[405],temp;
char str[405],ch1[2005],ch2[2005];
int i,j,len1,len2,len;
while(~scanf("%d%*c",&n))
{
scanf("%s",str);
memset(a,0,sizeof(a));
for(i=0;i<n;i++)
scanf("%d",&a[str[i]]);
getchar();
scanf("%s %s",ch1,ch2);
len1=strlen(ch1);
len2=strlen(ch2);
for(i=0;i<=len1;i++)
dp[i][0]=0;
for(j=0;j<=len2;j++)
dp[0][j]=0;
for(i=1;i<=len1;i++)
{
for(j=1;j<=len2;j++)
{
if(ch1[i-1]==ch2[j-1])
dp[i][j]=dp[i-1][j-1]+a[ch1[i-1]];
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
printf("%d
",dp[len1][len2]);
}
return 0;
}