vijos1059題解

題目：

XC的兒子小XC最喜歡玩的遊戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是一個比他爸爸XC還聰明的孩子，他發現壘城堡的時候，如果下面的積木比上面的積木大，那麼城堡便不容易倒。是以他在壘城堡的時候總是遵循這樣的規則。

小XC想把自己壘的城堡送給幼稚園裡漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們為了獲得更漂亮的城堡而引起争執。可是他發現自己在壘城堡的時候并沒有預先考慮到這一點。是以他現在要改造城堡。由于他沒有多餘的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應該使最後的城堡都盡可能的高。

任務：

請你幫助小XC編一個程式，根據他壘的所有城堡的資訊，決定應該移去哪些積木才能獲得最佳的效果。

基礎DP。 

f[i]表示是否能到達第I的高度。map[i]則來記錄每個高度有幾個城堡能夠達到。

var
  f:array[0..10000] of boolean;
  map:array[0..10000] of longint;
  a:array[0..100] of longint;
  l,n,i,j,ch,k:longint;
begin
  readln(n);
  for l:=1 to n do
    begin
      read(ch);
      k:=0;
      while ch<>-1 do
        begin
          inc(k);
          a[k]:=ch;
          read(ch);
        end;
      fillchar(f,sizeof(f),false);
      f[0]:=true;
      for i:=1 to k do
        for j:=10000-a[i] downto 0do
          if f[j] thenf[j+a[i]]:=true;
      for i:=0 to 10000 do
        if f[i] then inc(map[i]);
    end;
  for i:=10000 downto 0 do
    if map[i]=n then
      begin
        writeln(i);
        halt;
      end;
end.