TopCoder - 12349 SRM579 Round1 Div1 RockPaperScissors (概率dp)

题目大意：

有$n$个骰子，每个骰子有300个面，其中有$a_i,b_i,c_i$分别为石头/布/剪刀

每轮你选择出石头/剪刀/布，然后会从剩下的骰子中随机取一个再随机结果，但是你不知道取的是什么骰子

赢一局的权值为3，平局为1

求最优情况下最大的权值期望

$$\$$

题目分析：

显然当前的局面只和已经抽出的石头/布/剪刀的数量有关（因为这是你唯一的决策依据，也是唯一影响局面的）

乍一看非常抽象的决策过程，实在无法通过分析得到每一种局面下应该作出的决策

于是考虑能否直接把每一种局面出现的概率求出，决策后将期望线性相加

不妨把随机取出的骰子放在一个序列上，一个局面是由已经出现的骰子和当前第$i$次决策的骰子组成的

令$dp_{i,j,k,typ}$表示已经出现的骰子中出现$i,j,k$个石头/布/剪刀，当前决策时骰子结果为$typ$的概率

实际在$dp$时，$typ$一维需要额外加入一个值表示未确定下一个是什么

考虑对于每个骰子，枚举它是已经出现/正在决策/在第$i$次决策之后出现，将其概率累和

$dp$状态为$O(n^3)$，转移次数为$O(n)$,复杂度为$O(n^4)$

最后对于每种局面计算最优的决策即可

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

class RockPaperScissors {
private:
	static const int N=53;
	static const int eps=1e-9;
	double F[N][N][N][4],G[N][N][N][4],w[3];
	double C[N][N];

public:
	
	double bestScore(vector <int> w1, vector <int> w2, vector <int> w3) {
		int n=w1.size();
		rep(i,0,n) rep(j,C[i][0]=1,i) C[i][j]=C[i-1][j-1]+C[i-1][j];
		memset(F,0,sizeof F),F[0][0][0][3]=1;
		rep(i,1,n) {
			w[0]=w1[i-1]/300.0; w[1]=w2[i-1]/300.0; w[2]=w3[i-1]/300.0;
			rep(a,0,i) rep(b,0,i-a) rep(c,0,i-a-b) rep(d,0,3) G[a][b][c][d]=F[a][b][c][d];
			rep(a,0,i) rep(b,0,i-a) rep(c,0,i-a-b) rep(d,0,3) if(G[a][b][c][d]>eps) {
				// 枚举这个骰子在之前出现过了
				F[a+1][b][c][d]+=G[a][b][c][d]*w[0];
				F[a][b+1][c][d]+=G[a][b][c][d]*w[1];
				F[a][b][c+1][d]+=G[a][b][c][d]*w[2];
				// 枚举这个骰子为下一个出现的
				if(d==3) rep(e,0,2) F[a][b][c][e]+=G[a][b][c][d]*w[e];
			}
		}
		double ans=0;
		rep(a,0,n-1) rep(b,0,n-1-a) rep(c,0,n-1-a-b) {
			// 决策这一轮出什么
			double ma=0;
			rep(d,0,2) cmax(ma,F[a][b][c][d]+F[a][b][c][(d+2)%3]*3);
			ans+=ma/C[n][a+b+c]/(n-a-b-c);
		}
		return ans;
	}
};