首页 > 代码库 > Gym 101334D 记忆化dp
Gym 101334D 记忆化dp
大致题意：
给你9堆扑克牌，每堆牌有4张，大小从A~K。每次从9堆牌牌顶抽走两张大小相同的牌，且抽走每一对相同的牌的概率都相等。问可以全部抽完的概率。
分析：
这是一道概率dp题。剩余的牌数作为状态，有9堆，意味着要一个9维数组来存d[i1][i2][i3][i4][i5][i6][i7][i8][i9]表示这个状态的概率，0<=i<=4。
状态转移：
当前状态的概率等于抽走两张牌后所能达到的状态的概率和除以所能达到的状态数
边界d[0][0][0][0][0][0][0][0][0]=1
#include <bits/stdc++.h>using namespace std;char s[15][10];map<vector<int>,double> d;double dp(vector<int> cnt,int left){ if(left==0) return 1.0; if(d.count(cnt)) return d[cnt]; d[cnt]=0; int tmp=0; double res = 0; for(int i=1;i<=9;i++) { if(cnt[i]==0) continue; for(int j=i+1;j<=9;j++) { if(cnt[j]==0) continue; if(s[i][cnt[i]]==s[j][cnt[j]]) { cnt[i]--; cnt[j]--; //debug(cnt); res+=dp(cnt,left-2); cnt[i]++; cnt[j]++; tmp++; } } } if(tmp>0) d[cnt]=res/tmp; return d[cnt];}int main(){// freopen("in.txt","r",stdin); freopen("double.in","r",stdin); freopen("double.out","w",stdout); char ts[5]; for(int i=1;i<=9;i++) { for(int j=1;j<=4;j++) { scanf("%s",ts); s[i][j]=ts[0]; } } vector<int> cnt(10,4); d.clear(); printf("%.6f\n",dp(cnt,36)); return 0;}
Gym 101334D 记忆化dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。