4832: [Lydsy2017年4月月賽]抵制克蘇恩

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?441??Solved:?162
[Submit][Status][Discuss]

Description

小Q同學(xué)現(xiàn)在沉迷爐石傳說不能自拔。他發(fā)現(xiàn)一張名為克蘇恩的牌很不公平。如果你不玩爐石傳說，不必?fù)?dān)心，小Q 同學(xué)會告訴你所有相關(guān)的細(xì)節(jié)。爐石傳說是這樣的一個游戲，每個玩家擁有一個 30 點血量的英雄，并且可以用牌 召喚至多 7 個隨從幫助玩家攻擊對手，其中每個隨從也擁有自己的血量和攻擊力。小Q同學(xué)有很多次游戲失敗都是 因為對手使用了克蘇恩這張牌，所以他想找到一些方法來抵御克蘇恩。他去求助職業(yè)爐石傳說玩家椎名真白，真白 告訴他使用奴隸主這張牌就可以啦。如果你不明白我上面在說什么，不必?fù)?dān)心，小Q同學(xué)會告訴你他想讓你做什么 。現(xiàn)在小Q同學(xué)會給出克蘇恩的攻擊力是 K ，表示克蘇恩會攻擊 K 次，每次會從對方場上的英雄和隨從中隨機選 擇一個并對其產(chǎn)生 1 點傷害。現(xiàn)在對方有一名克蘇恩，你有一些奴隸主作為隨從，每名奴隸主的血量是給定的。 如果克蘇恩攻擊了你的一名奴隸主，那么這名奴隸主的血量會減少 1 點，當(dāng)其血量小于等于 0 時會死亡，如果受 到攻擊后不死亡，并且你的隨從數(shù)量沒有達到 7 ，這名奴隸主會召喚一個擁有 3 點血量的新奴隸主作為你的隨從 ；如果克蘇恩攻擊了你的英雄，你的英雄會記錄受到 1 點傷害。你應(yīng)該注意到了，每當(dāng)克蘇恩進行一次攻擊，你 場上的隨從可能發(fā)生很大的變化。小Q同學(xué)為你假設(shè)了克蘇恩的攻擊力，你場上分別有 1 點、 2 點、 3 點血量的 奴隸主數(shù)量，你可以計算出你的英雄受到的總傷害的期望值是多少嗎？

Input

輸入包含多局游戲。 第一行包含一個整數(shù) T (T<100) ，表示游戲的局?jǐn)?shù)。 每局游戲僅占一行，包含四個非負(fù)整數(shù) K, A, B 和 C ，表示克蘇恩的攻擊力是 K ，你有 A 個 1 點血量的奴隸 主， B 個 2 點血量的奴隸主， C 個 3 點血量的奴隸主。 保證 K 是小于 50 的正數(shù)， A+B+C 不超過 7 。

Output

對于每局游戲，輸出一個數(shù)字表示總傷害的期望值，保留兩位小數(shù)。

Sample Input

1
1 1 1 1

Sample Output

0.25 solution: ? ??　　本蒟蒻玩爐石傳說很垃圾，當(dāng)然啦這題和游戲其實關(guān)系不大。 　　 ? ?第一眼看到題就肯定是個概率dp，并且狀態(tài)數(shù)組也很好想，四維數(shù)組，f[i][a][b][c]代表攻擊到第i次還有a個一滴血奴隸主b個2滴血奴隸主c個3滴血奴隸主時英雄期望受到的傷害值。 　　 ?f[0][A][B][C]=1; 狀態(tài)轉(zhuǎn)移方程也很好想： 　　 ??f[i+1][a-1][b][c]+=f[i][a][b][c]*a/(1+a+b+c); ? ? ?（a>0） 　　 ??f[i+1][a+1][b-1][c+1]+=f[i][a][b][c]*b/(1+a+b+c); ? (b>0且a+b+c<7) 　　 ??f[i+1][a+1][b-1][c]+=f[i][a][b][c]*b/(1+a+b+c); ? ? (b>0且a+b+c==7) 　　 ??f[i+1][a][b+1][c]+=f[i][a][b][c]*c/(1+a+b+c); ? ? ?（c>0且a+b+c<7） 　　 ??f[i+1][a][b+1][c-1]+=f[i][a][b][c]*c/(1+a+b+c); ? ? (c>0且a+b+c==7) 　　　四層循環(huán)暴力轉(zhuǎn)移，但要注意的是每次的總?cè)藬?shù)應(yīng)為a+b+c+1，本蒟蒻考試的時候少打了一個1，結(jié)果全wa了，無奈，加上1在內(nèi)網(wǎng)上一交就A了。 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 #define eps 1e-10 8 int read() { 9 int s=0,f=1; 10 char ch=getchar(); 11 while(ch>'9'||ch<'0') { 12 if(ch=='-') { 13 f=-1; 14 } 15 ch=getchar(); 16 } 17 while(ch>='0'&&ch<='9') { 18 s=(s<<1)+(s<<3)+(ch^48); 19 ch=getchar(); 20 } 21 return s*f; 22 } 23 int T,k,A,B,C; 24 double ans; 25 double f[59][10][10][10]; 26 void init() { 27 memset(f,0,sizeof(f)); 28 f[0][A][B][C]=1; 29 } 30 void work() { 31 for(int i=0; i<k; i++) { 32 for(int a=0; a<8; a++) { 33 for(int b=0; b<8; b++) { 34 for(int c=0; c<8; c++) { 35 if(a+b+c>7) { 36 continue; 37 }//攻擊隨從 38 //cout<<a<<endl; 39 if(a>0) { //a被攻擊死亡不會產(chǎn)c 40 f[i+1][a-1][b][c]+=f[i][a][b][c]*(double)a/(double)(1+a+b+c); 41 } 42 if(b>0) { 43 if(a+b+c<7) { //b被攻擊 總和小于7 產(chǎn)c 44 f[i+1][a+1][b-1][c+1]+=f[i][a][b][c]*(long double)b/(long double)(1+a+b+c); 45 } 46 if(a+b+c>=7) { //b被攻擊 總和等于7 不產(chǎn)c 47 f[i+1][a+1][b-1][c]+=f[i][a][b][c]*(long double)b/(long double)(1+a+b+c); 48 } 49 } 50 if(c>0) { 51 if(a+b+c<7) { //c被攻擊 總和小于7 52 f[i+1][a][b+1][c]+=f[i][a][b][c]*(long double)c/(long double)(1+a+b+c); 53 } 54 if(a+b+c>=7) { //c被攻擊 總和等于7 55 f[i+1][a][b+1][c-1]+=f[i][a][b][c]*(long double)c/(long double)(1+a+b+c); 56 } 57 } 58 f[i+1][a][b][c]+=f[i][a][b][c]/(long double)(a+b+c+1);//英雄被攻擊 59 ans+=f[i][a][b][c]/(a+b+c+1.0); 60 } 61 } 62 } 63 } 64 } 65 int main() { 66 //freopen("defcthun.in","r",stdin); 67 //freopen("defcthun.out","w",stdout); 68 T=read(); 69 while(T--) { 70 ans=0; 71 k=read(); 72 A=read(); 73 B=read(); 74 C=read(); 75 init(); 76 work(); 77 printf("%0.2lf\n",ans); 78 } 79 //fclose(stdin); 80 //fclose(stdout); 81 return 0; 82 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/forevergoodboy/p/7260025.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的bzoj 4832 抵制克苏恩的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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