【NOIP复赛模拟题(一)】【第2题...
2237 ワード
【NOIP再試合シミュレーション問題(一)】【第2題】暗号解読
Time Limit:1000MS Memory Limit:32768K Total Submit:9 Accepted:5
Description
解読パスワード(password.pas/c/cpp)【題名説明】Feliは本部からのメッセージを得て、わが軍の特殊部隊はすでに敵のパスワード帳を切り取ったが、このパスワード帳自体はパスワードで書かれている.敵に重い打撃を与えるために、Feliはできるだけ早くパスワードを解読しなければならない.一日一夜の探索を経て、Feliは日本軍の暗号本に実際に数列が記載されていることを発見し、最終的に暗号はこの数列から何らかの演算を経て得られた.演算はこうです:1.数列を小さいから大きいまで並べ替える. 2.(分割)順序付けされた数列のうち、原数列を左右の2つの数列に分割する数を選択します(選択された数は新数列になく、新数列が空である可能性があります). 3.最終的に得られた数列の長さが1になるまで、新しい数列ごとに2ステップ目の操作を行います.すなわち、すべてが単一の数になります. 4.ステップ3で得られた各数*(必要な分割数+1を得る)を加算して1つの和を得る. 5.2,3,4操作を繰り返し、すべての分割が可能になるまで繰り返します.このとき、得られた和の中で一番小さいのが日本軍の最終パスワードです. 6.今Feliはあなたに助けを求めて、できるだけ早くこのパスワードを解読します!
Input
入力ファイルpassword.in第1の挙動N,N≦1000は,暗号帳に記録された数列の長さを表す.次の行にはN個の数、すなわち日本軍暗号帳に記載されている数列がある.
Output
出力ファイルpassword.outは整数、すなわち日本軍の最終パスワードである.
Sample Input
Sample Output
Hint
【サンプル説明】1.数列を1 2 3に並べ替える.数2 3を選択する.分割2/1 3このときの新しい数列(1,3)の長さはいずれも1であるため、分割4は不要である.和を求めて、2*1+1*2+3*2=10(2は元の数の列にあるので、1に乗る;1と3はすべて一回の分割を経て、だから2に乗る)2.1つの数3を選択する.分割して12 3 2 3の中から1つの数2を選択し、分割して123 4を得る.和を求めて、1*1+2*2+3*3=14……すべての和の中で最も小さいのは10で、だから出力10
Source
最初は木の形の動帰かと思っていたので、そのまま探しました.
実は区間動帰です.ここでは、四角形の不等式を使用します.
具体的には私にもわかりません.の
var n:longint; a:array[0..1000+1]of longint; f,q,w:array[0..1000+1,0..1000+1]of longint;
procedure init; var i,j:longint; begin read(n); for i:=1 to n do read(a[i]); for i:=1 to n-1 do for j:=i+1 to n do if a[i]>a[j] then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; end; end; procedure main; var i,j,k,l,minl,min:longint; begin for i:=1 to n do w[i,i]:=a[i]; for i:=1 to n-1 do for j:=i+1 to n do w[i,j]:=w[i,j-1]+a[j];
for i:=1 to n do f[i,i]:=a[i]; for i:=1 to n do q[i,i]:=i;
for k:=2 to n do for i:=1 to n-k+1 do begin j:=i+k-1; min:=maxlongint; for l:=q[i,j-1] to q[i+1,j] do if f[i,l-1]+f[l+1,j] begin min:=f[i,l-1]+f[l+1,j]; minl:=l; end; f[i,j]:=min+w[i,j]; q[i,j]:=minl; end; write(f[1,n]); end;
begin assign(input,'password.in'); assign(output,'password.out'); reset(input); rewrite(output); init; main; close(input); close(output); end.
Time Limit:1000MS Memory Limit:32768K Total Submit:9 Accepted:5
Description
解読パスワード(password.pas/c/cpp)【題名説明】Feliは本部からのメッセージを得て、わが軍の特殊部隊はすでに敵のパスワード帳を切り取ったが、このパスワード帳自体はパスワードで書かれている.敵に重い打撃を与えるために、Feliはできるだけ早くパスワードを解読しなければならない.一日一夜の探索を経て、Feliは日本軍の暗号本に実際に数列が記載されていることを発見し、最終的に暗号はこの数列から何らかの演算を経て得られた.演算はこうです:1.数列を小さいから大きいまで並べ替える. 2.(分割)順序付けされた数列のうち、原数列を左右の2つの数列に分割する数を選択します(選択された数は新数列になく、新数列が空である可能性があります). 3.最終的に得られた数列の長さが1になるまで、新しい数列ごとに2ステップ目の操作を行います.すなわち、すべてが単一の数になります. 4.ステップ3で得られた各数*(必要な分割数+1を得る)を加算して1つの和を得る. 5.2,3,4操作を繰り返し、すべての分割が可能になるまで繰り返します.このとき、得られた和の中で一番小さいのが日本軍の最終パスワードです. 6.今Feliはあなたに助けを求めて、できるだけ早くこのパスワードを解読します!
Input
入力ファイルpassword.in第1の挙動N,N≦1000は,暗号帳に記録された数列の長さを表す.次の行にはN個の数、すなわち日本軍暗号帳に記載されている数列がある.
Output
出力ファイルpassword.outは整数、すなわち日本軍の最終パスワードである.
Sample Input
Sample Output
Hint
【サンプル説明】1.数列を1 2 3に並べ替える.数2 3を選択する.分割2/1 3このときの新しい数列(1,3)の長さはいずれも1であるため、分割4は不要である.和を求めて、2*1+1*2+3*2=10(2は元の数の列にあるので、1に乗る;1と3はすべて一回の分割を経て、だから2に乗る)2.1つの数3を選択する.分割して12 3 2 3の中から1つの数2を選択し、分割して123 4を得る.和を求めて、1*1+2*2+3*3=14……すべての和の中で最も小さいのは10で、だから出力10
Source
最初は木の形の動帰かと思っていたので、そのまま探しました.
実は区間動帰です.ここでは、四角形の不等式を使用します.
具体的には私にもわかりません.の
var n:longint; a:array[0..1000+1]of longint; f,q,w:array[0..1000+1,0..1000+1]of longint;
procedure init; var i,j:longint; begin read(n); for i:=1 to n do read(a[i]); for i:=1 to n-1 do for j:=i+1 to n do if a[i]>a[j] then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; end; end; procedure main; var i,j,k,l,minl,min:longint; begin for i:=1 to n do w[i,i]:=a[i]; for i:=1 to n-1 do for j:=i+1 to n do w[i,j]:=w[i,j-1]+a[j];
for i:=1 to n do f[i,i]:=a[i]; for i:=1 to n do q[i,i]:=i;
for k:=2 to n do for i:=1 to n-k+1 do begin j:=i+k-1; min:=maxlongint; for l:=q[i,j-1] to q[i+1,j] do if f[i,l-1]+f[l+1,j] begin min:=f[i,l-1]+f[l+1,j]; minl:=l; end; f[i,j]:=min+w[i,j]; q[i,j]:=minl; end; write(f[1,n]); end;
begin assign(input,'password.in'); assign(output,'password.out'); reset(input); rewrite(output); init; main; close(input); close(output); end.