P2002 撲克牌 時間: 1000ms / 空間: 131072KiB / Java類名: Main

背景

Admin生日那天，Rainbow來找Admin玩撲克牌……
玩著玩著Rainbow覺得太沒意思了,于是決定給Admin一個考驗~~~

描述

Rainbow把一副撲克牌(54張)隨機洗開，倒扣著放成一摞。然后Admin從上往下依次翻開每張牌，每翻開一張黑桃、紅桃、梅花或者方塊，就把它放到對應花色的堆里去。
Rainbow想問問Admin，得到A張黑桃、B張紅桃、C張梅花、D張方塊需要翻開的牌的張數的期望值E是多少？
特殊地，如果翻開的牌是大王或者小王，Admin將會把它作為某種花色的牌放入對應堆中,使得放入之后E的值盡可能小。
由于Admin和Rainbow還在玩撲克，所以這個程序就交給你來寫了~

輸入格式

輸入僅由一行，包含四個用空格隔開的整數，A,B,C,D。

輸出格式

輸出需要翻開的牌數的期望值E，四舍五入保留3位小數。
如果不可能達到輸入的狀態，輸出-1.000。

測試樣例1

輸入

樣例輸入1
1 2 3 4

樣例輸入2
15 15 15 15

輸出

樣例輸出1
16.393

樣例輸出2
-1.000

備注

對于100%的數據，0<=A,B,C,D<=15

lydrainbowcat?-?"Admin生日"杯NOIP模擬賽?第三題

————————————————————我是分割線————————————————————————

好題。

數學期望DP
用記憶化搜索實現。

數組竟然六維，可怕......

1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include<iomanip> 5 #include <algorithm> 6 #include <iostream> 7 using namespace std; 8 double dp[15][15][15][15][5][5]; 9 bool vis[15][15][15][15][5][5]; 10 int t[4]; 11 double dfs(int a,int b,int c,int d,int e,int f) 12 { 13 if (vis[a][b][c][d][e][f]) return dp[a][b][c][d][e][f]; 14 if (((a+(e==0)+(f==0))>=t[0])&&((b+(e==1)+(f==1))>=t[1])&&((c+(e==2)+(f==2))>=t[2])&&((d+(e==3)+(f==3))>=t[3])) return dp[a][b][c][d][e][f]=0.0; 15 int sum=a+b+c+d+(e!=4)+(f!=4); 16 double F=1; 17 if (a<13) F+=dfs(a+1,b,c,d,e,f)*(13-a)/(54-sum); 18 if (b<13) F+=dfs(a,b+1,c,d,e,f)*(13-b)/(54-sum); 19 if (c<13) F+=dfs(a,b,c+1,d,e,f)*(13-c)/(54-sum); 20 if (d<13) F+=dfs(a,b,c,d+1,e,f)*(13-d)/(54-sum); 21 double md=100; if (e==4) {for (int i=0;i<4;++i) md=min(dfs(a,b,c,d,i,f)/(54-sum),md); F+=md;} 22 md=100; if (f==4) {for (int i=0;i<4;++i) md=min(dfs(a,b,c,d,e,i)/(54-sum),md); F+=md;} 23 vis[a][b][c][d][e][f]=true; 24 return dp[a][b][c][d][e][f]=F; 25 } 26 int main() 27 { 28 memset(vis,false,sizeof vis); 29 int a,b,c,d; 30 scanf("%d%d%d%d",&t[0],&t[1],&t[2],&t[3]); 31 a=t[0];b=t[1];c=t[2];d=t[3]; 32 double ans=dfs(0,0,0,0,4,4); 33 if (ans>54.0) printf("-1.000\n"); 34 else cout<<setiosflags(ios::fixed)<<setprecision(3)<<ans; 35 } tyvj 2002

?

轉載于:https://www.cnblogs.com/SBSOI/p/5636538.html

總結

以上是生活随笔為你收集整理的TYVJ 2002 扑克牌 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

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