Codevs P1997 守衛者的挑戰

題目描述 Description

　　打開了黑魔法師Vani的大門，隊員們在迷宮般的路上漫無目的地搜尋着關押applepi的監獄的所在地。突然，眼前一道亮光閃過。“我，Nizem，是黑魔法聖殿的守衛者。如果你能通過我的挑戰，那麼你可以帶走黑魔法聖殿的地圖……”瞬間，隊員們被傳送到了一個擂台上，最初身邊有一個容量為K的包包。

　　擂台賽一共有項挑戰，各項挑戰依次進行。第項挑戰有一個屬性ai，如果ai≥0，表示這次挑戰成功後可以再獲得一個容量為ai的包包；如果ai = -1，則表示這次挑戰成功後可以得到一個大小為 1 的地圖殘片。地圖殘片必須裝在包包裡才能帶出擂台，包包沒有必要全部裝滿，但是隊員們必須把獲得的所有的地圖殘片都帶走（沒有得到的不用考慮，隻需要完成所有N項挑戰後背包容量足夠容納地圖殘片即可），才能拼出完整的地圖。并且他們至少要挑戰成功L次才能離開擂台。

　　隊員們一籌莫展之時，善良的守衛者Nizem幫忙預估出了每項挑戰成功的機率，其中第i項挑戰成功的機率為pi %。現在，請你幫忙預測一下，隊員們能夠帶上他們獲得的地圖殘片離開擂台的機率。

輸入輸出 Input&Output

輸入描述 Input Description

　　第一行三個整數N，L，K。

　　第二行N個實數，第i個實數pi表示第i項挑戰成功的百分比。

　　第三行N個整數，第i個整數ai表示第i項挑戰的屬性值。

輸出描述 Output Description

　　一個整數，表示所求機率，強制四舍五入保留6位小數。

樣例 Sample

樣例輸入 Sample Input

【樣例輸入1】

3 1 0

10 20 30

-1 -1 2

【樣例輸入2】

5 1 2

36 44 13 83 63

-1 2 -1 2 1

樣例輸出 Sample Output

【樣例輸出1】

0.300000

【樣例輸出2】

0.980387

資料範圍及提示 Data Size & Hint

　　在第一個樣例中，若第三項挑戰成功，如果前兩場中某場勝利，隊員們就有空間來容納得到的地圖殘片，如果挑戰失敗，根本就沒有獲得地圖殘片，不用考慮是否能裝下；若第三項挑戰失敗，如果前兩場有勝利，沒有包來裝地圖殘片，如果前兩場都失敗，不滿足至少挑戰成功L次（L = 1）的要求。是以所求機率就是第三場挑戰獲勝的機率。

　　對于 100% 的資料，保證0≤K≤2000，0≤N≤200，-1≤ai≤1000，0≤L≤N，0≤pi≤100。

來源：Nescafe 17

分析

先将獎賞按從大到小排列，這樣搜到時如果背包體積>0則是可行的<0則不可行。因為已經按照從大到小排序，獲得的背包早就獲得完畢，再出現負值肯定不能再有包裝進去。

設f[i,j,k]表示前i場中赢j場容量為k的機率

那麼f[i+1,j,k]:=f[i+1,j,k]f[i,j,k]*(1-p[i+1]) 累加上第i+1場未獲勝的機率

如果第i+1場獲勝那麼得到num[i+1]的背包或地圖，是以i+1場勝利時容量為k+num[i+1]，當小于0時無意義，表示背包不夠。

是以如果k+num[i+1]>0和n取較小值，大于n沒有用處。

是以當第i+1場勝利時

now：=k+num[i+1]

now：=min（now，n）；

f[i+1,j+1,now]：=f[i+1,j+1,now]+f[i,j,k]*p[i+1];

最終答案就是打完n場後勝利l場以上的背包容量>=0的機率和。>=0表示地圖已全部被裝下。

代碼如下

program p1997;
var now,n,l,k,i,j,s,e:longint;
    p:array[..] of double;
    num:array[..] of integer;
    f:array[..,..,..] of double;
    ans:double;
function min(a,b:longint):longint;
begin
 if a<b then exit(a);
 exit(b);
end;

procedure qsort(l,r:longint);
var i,j,mid:longint;
    temp1:longint;
    temp2:double;
begin
 i:=l;
 j:=r;
 mid:=num[(i+j)>>];
 while i<=j do
  begin
   while num[i]>mid do inc(i);
   while num[j]<mid do dec(j);
   if i<=j
    then
     begin
      temp1:=num[i];
      temp2:=p[i];
      num[i]:=num[j];
      p[i]:=p[j];
      num[j]:=temp1;
      p[j]:=temp2;
      inc(i);
      dec(j);
     end;
  end;
 if i<r then qsort(i,r);
 if l<j then qsort(l,j);
end;

begin
 readln(n,l,k);
 for i:= to n do
  begin
   read(p[i]);
   p[i]:=p[i]/;
  end;
 for i:= to n do
  read(num[i]);
 qsort(,n);
 f[,,min(k,n)]:=;
 for i:= to n- do
  for j:= to i do
   for s:= to n do
    begin
     f[i+,j,s]:=f[i+,j,s]+f[i,j,s]*(-p[i+]);
     now:=s+num[i+];
     if now< then continue;
     now:=min(now,n);
     f[i+,j+,now]:=f[i+,j+,now]+f[i,j,s]*(p[i+]);
    end;
 for i:= to n do
  for j:=l to n do
   ans:=ans+f[n,j,i];
 write(ans::);
end.
           

評測結果

測試點#guard1.in 結果:AC 記憶體使用量: 256kB 時間使用量: 0ms

測試點#guard10.in 結果:AC 記憶體使用量: 32880kB 時間使用量: 102ms

測試點#guard2.in 結果:AC 記憶體使用量: 368kB 時間使用量: 0ms

測試點#guard3.in 結果:AC 記憶體使用量: 256kB 時間使用量: 0ms

測試點#guard4.in 結果:AC 記憶體使用量: 1136kB 時間使用量: 0ms

測試點#guard5.in 結果:AC 記憶體使用量: 1264kB 時間使用量: 1ms

測試點#guard6.in 結果:AC 記憶體使用量: 2412kB 時間使用量: 4ms

測試點#guard7.in 結果:AC 記憶體使用量: 8556kB 時間使用量: 17ms

測試點#guard8.in 結果:AC 記憶體使用量: 8556kB 時間使用量: 18ms

測試點#guard9.in 結果:AC 記憶體使用量: 18800kB 時間使用量: 48ms

擔心。。