Description

小 K 不慎被 LL 邪教洗腦了，洗腦程度深到他甚至想要從亞瑟王邪教中脫坑。

他決定，在脫坑之前，最后再來打一盤亞瑟王。既然是最后一戰，就一定要打得漂 亮。眾所周知，亞瑟王是一個看臉的游戲，技能的發動都是看概率的。作為一個非 洲人，同時作為一個前 OIer，小 K 自然是希望最大化造成傷害的期望值。但他已 經多年沒寫過代碼，連 Spaly都敲不對了，因此，希望你能幫幫小 K，讓他感受一 下當歐洲人是怎樣的體驗。? 本題中我們將考慮游戲的一個簡化版模型。? 玩家有一套卡牌，共 n張。游戲時，玩家將 n 張卡牌排列成某種順序，排列后 將卡牌按從前往后依次編號為 1 ~ ?n。本題中，順序已經確定，即為輸入的順序。 每張卡牌都有一個技能。第 i 張卡牌的技能發動概率為 pi，如果成功發動，則會對 敵方造成di點傷害。也只有通過發動技能，卡牌才能對敵方造成傷害。基于現實因 素以及小K非洲血統的考慮，pi不會為 0，也不會為 1，即 0 < pi < 1。? 一局游戲一共有 r 輪。在每一輪中，系統將從第一張卡牌開始，按照順序依次 考慮每張卡牌。在一輪中，對于依次考慮的每一張卡牌：? 1如果這張卡牌在這一局游戲中已經發動過技能，則? 1.1 如果這張卡牌不是最后一張，則跳過之（考慮下一張卡牌）；? 否則（是最后一張），結束這一輪游戲。? 2否則（這張卡牌在這一局游戲中沒有發動過技能），設這張卡牌為第 i 張? 2.1將其以 pi的概率發動技能。? 2.2如果技能發動，則對敵方造成 di點傷害，并結束這一輪。? 2.3如果這張卡牌已經是最后一張（即 i 等于n），則結束這一輪；否則， 考慮下一張卡牌。? 請幫助小 K 求出這一套卡牌在一局游戲中能造成的傷害的期望值。?

Input

輸入文件的第一行包含一個整數 T，代表測試數據組數。?

接下來一共 T 組數據。? 每組數據的第一行包含兩個用空格分開的整數 n和r，分別代表卡牌的張數和 游戲的輪數。? 接下來 n行，每行包含一個實數和一個整數，由空格隔開，描述一張卡牌。第 i 行的兩個數為 pi和 di，分別代表第 i 張卡牌技能發動的概率（實數）和技能發動 造成的傷害（整數）。保證 pi最多包含 4位小數，且為一個合法的概率。?

Output

?對于每組數據，輸出一行，包含一個實數，為這套卡牌在這一局游戲中造成的

傷害的期望值。對于每一行輸出，只有當你的輸出和標準答案的相對誤差不超過 10^-8時——即|a-o|/a<=10-8時(其中a是標準答案，o是輸出)，你的輸出才會被判為正確。 建議輸出10 位小數。?

Sample Input

1
3 2
0.5000 2
0.3000 3
0.9000 1

Sample Output

3.2660250000 對于所有測試數據， 1 <= T <= 444， 1 <= n <= 220， 0 <= r <= 132， 0 < pi < 1， 0 <= di <= 1000。 ? 除非備注中有特殊說明，數據中 pi與di均為隨機生成。? 請注意可能存在的實數精度問題，并采取適當措施。? 題解 先膜一波XYZ大神 這道題首先我們要想好狀態數組含義 由于這是個抽卡游戲,每抽到一張卡其他卡的概率都會改變 所以我們要消除這種不方便,故設f[i][j]表示前i張卡在游戲中剩下j輪被選擇的概率 對于第i-1張卡,考慮它對前i張的貢獻:要么在剩下j輪都沒被打出,要么它一定在某一輪中放了技能 所以這張卡對前i張卡的影響是 j輪都沒打出:f[i][j]+=f[i-1][j]*pow(1-p[i-1],j) 某一輪打出了:f[i][j-1]+=f[i-1][j]*(1-pow(1-p[i-1],j)); 所以f[i][j]的遞推公式是:f[i][j]=f[i-1][j]*pow(1-p[i-1],j)+f[i-1][j+1]*(1-pow(1-p[i-1],j+1)); 然后把所有f[i][j]乘上在j輪中某一輪打出的概率(1-pow(1-p[i],j)),再乘傷害d[i]然后累加,得到的就是最后答案 代碼見下 #include<cstdio> #include<cstring> #include<cmath> using namespace std; const int N=250; const int R=150; int t,n,r,d[N]; double p[N],k[N],f[N][R]; inline void intn() {for(int i=0;i<N;i++)p[i]=k[i]=0;memset(d,0,sizeof(d)); } int main() {scanf("%d",&t);while(t--){intn();scanf("%d%d",&n,&r);for(int i=1;i<=n;i++)scanf("%lf%d",&p[i],&d[i]);for(int i=0;i<N;i++)for(int j=0;j<R;j++)f[i][j]=0;double ans=0;f[0][r]=1;for(int i=1;i<=n;i++)for(int j=1;j<=r;j++){f[i][j]=f[i-1][j]*pow(1-p[i-1],j)+f[i-1][j+1]*(1-pow(1-p[i-1],j+1));ans+=f[i][j]*(1-pow(1-p[i],j))*d[i];}printf("%.10lf\n",ans);} }

?

轉載于:https://www.cnblogs.com/LadyLex/p/7006906.html

總結

以上是生活随笔為你收集整理的[BZOJ4008]亚瑟王的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。