UVA - 1637 Double Patience(全概率+记忆化搜索)
题目链接
Reference:https://blog.csdn.net/weijifen000/article/details/82262821
设当前状态为 a a a,那么可以转移到下面的若干个状态 b i b_i bi
设事件 W W W为“游戏成功”,事件 A A A为“实现状态 A A A”,事件 B i B_i Bi为“出现状态 b i b_i bi”,则事件 ( A ∣ B i ) (A∣Bi) (A∣Bi)为“出现状态 b i b_i bi的条件下游戏成功”,事件 ( W ∣ A ) (W∣A) (W∣A)为“在状态 a a a的条件下游戏成功”,则根据全概率公式
P ( W ) = P ( W ∣ B 1 ) ∗ P ( B 1 ) + P ( W ∣ B 2 ) ∗ P ( B 2 ) + . . . + P ( W ∣ B n ) ∗ P ( B n ) P(W)=P(W∣B_1)*P(B_1)+P(W∣B_2)*P(B_2)+...+P(W∣B_n)*P(B_n) P(W)=P(W∣B1)∗P(B1)+P(W∣B2)∗P(B2)+...+P(W∣Bn)∗P(Bn)
然后因为转移到每个状态是等可能的,只和转移的状态总数有关,那么就是所有状态的概率求和除以总数
看LRJ分析提到搜索,我一开始想的是,写一个9元数组?但是状态太多无法表示,不可能这样
然后去参考了网上的代码,学到了很多:
- 这种只输入多个字符串且有空格的,使用 c i n cin cin,而且最好写一个 r e a d ( ) read() read()函数,没有输入就是 ! ( c i n > > . . . ) !(cin>>...) !(cin>>...),这样不易错
- 状态太多时使用
map<vector<int>,double>
代替vis数组,可以记忆化某个状态是否已经访问以及保存已访问的结果 - 传递当前纸牌的个数使得特判更加方便
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;
char dic[10][5][5];
map<vector<int>,double> mp;
bool read(){
for(int i=0;i<9;i++)
for(int j=0;j<4;j++)
if(!(cin>>dic[i][j]))
return false;
return true;
}
double dfs(vector<int>& res,int num){
if(num==0) return 1.0;
if(mp.count(res)) return mp[res];
double sum=0;
int cnt=0;
for(int i=0;i<9;i++) if(res[i]>0)
for(int j=i+1;j<9;j++) if(res[j]>0)
if(dic[i][res[i]-1][0]==dic[j][res[j]-1][0]){
cnt++;
res[i]--;
res[j]--;
sum+=dfs(res,num-2);
res[i]++;
res[j]++;
}
if(!cnt) return mp[res]=0;
return mp[res]=sum/cnt;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
while(read()){
vector<int> tmp(9,4);
mp.clear();
printf("%.6f\n",dfs(tmp,36));
}
return 0;
}