【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.