Description
打開(kāi)了黑魔法師Vani的大門(mén)，隊(duì)員們?cè)诿詫m般的路上漫無(wú)目的地搜尋著關(guān)押applepi的監(jiān)獄的所在地。突然，眼前一道亮光閃過(guò)。“我，Nizem，是黑魔法圣殿的守衛(wèi)者。如果你能通過(guò)我的挑戰(zhàn)，那么你可以帶走黑魔法圣殿的地圖……”瞬間，隊(duì)員們被傳送到了一個(gè)擂臺(tái)上，最初身邊有一個(gè)容量為K的包包。

擂臺(tái)賽一共有N項(xiàng)挑戰(zhàn)，各項(xiàng)挑戰(zhàn)依次進(jìn)行。第i項(xiàng)挑戰(zhàn)有一個(gè)屬性ai，如果ai>=0，表示這次挑戰(zhàn)成功后可以再獲得一個(gè)容量為ai的包包；如果ai=-1，則表示這次挑戰(zhàn)成功后可以得到一個(gè)大小為1 的地圖殘片。地圖殘片必須裝在包包里才能帶出擂臺(tái)，包包沒(méi)有必要全部裝滿(mǎn)，但是隊(duì)員們必須把 獲得的所有的地圖殘片都帶走（沒(méi)有得到的不用考慮，只需要完成所有N項(xiàng)挑戰(zhàn)后背包容量足夠容納地圖殘片即可），才能拼出完整的地圖。并且他們至少要挑戰(zhàn)成功L次才能離開(kāi)擂臺(tái)。

隊(duì)員們一籌莫展之時(shí)，善良的守衛(wèi)者Nizem幫忙預(yù)估出了每項(xiàng)挑戰(zhàn)成功的概率，其中第i項(xiàng)挑戰(zhàn)成功的概率為pi%。現(xiàn)在，請(qǐng)你幫忙預(yù)測(cè)一下，隊(duì)員們能夠帶上他們獲得的地圖殘片離開(kāi)擂臺(tái)的概率。

Input
第一行三個(gè)整數(shù)N,L,K。

第二行N個(gè)實(shí)數(shù)，第i個(gè)實(shí)數(shù)pi表示第i項(xiàng)挑戰(zhàn)成功的百分比。

第三行N個(gè)整數(shù)，第i個(gè)整數(shù)ai表示第i項(xiàng)挑戰(zhàn)的屬性值.

Output
一個(gè)整數(shù)，表示所求概率，四舍五入保留6 位小數(shù)。

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

樣例解釋：

若第三項(xiàng)挑戰(zhàn)成功，如果前兩場(chǎng)中某場(chǎng)勝利，隊(duì)員們就有空間來(lái)容納得到的地圖殘片，如果挑戰(zhàn)失敗，根本就沒(méi)有獲得地圖殘片，不用考慮是否能裝下；若第三項(xiàng)挑戰(zhàn)失敗，如果前兩場(chǎng)有勝利，沒(méi)有包來(lái)裝地圖殘片，如果前兩場(chǎng)都失敗，不滿(mǎn)足至少挑戰(zhàn)成功L次（L=1）的要求。因此所求概率就是第三場(chǎng)挑戰(zhàn)獲勝的概率。

樣例輸出2

0.980387

Data Constraint
對(duì)于 100% 的數(shù)據(jù)，保證0<=K<=2000，0<=N<=200，-1<=ai<=1000，0<=L<=N，0<=pi<=100。
.
.
.
.
.

分析

.
.
.
.
.

程序：

#include<iostream> #include<cstdio> using namespace std; double f[201][201][401],p[201],ans=0; int n,l,k,a[201];void check(int x,int y,int z,double w) {if (z>n) z=n;f[x][y][z+200]+=w; }int main() {cin>>n>>l>>k;for (int i=1;i<=n;i++){int x;cin>>x;p[i]=(double)x/100.0;}for (int i=1;i<=n;i++) cin>>a[i];if (k>n) k=n;f[0][0][k+200]=1;for (int i=0;i<n;i++)for (int j=0;j<=i;j++)for (int k=-i;k<=n;k++){check(i+1,j+1,k+a[i+1],p[i+1]*f[i][j][k+200]);check(i+1,j,k,(1-p[i+1])*f[i][j][k+200]);}for (int i=0;i<=n;i++) for (int j=l;j<=n;j++) ans+=f[n][j][i+200];printf("%.6lf",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499925.html

總結(jié)

以上是生活随笔為你收集整理的【NOIP2013模拟】守卫者的挑战(期望概率)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。