猜拳游戏

猜拳游戏(01规划)

题目描述

YYC和他的妹子nayC在玩石头剪刀布，但是这太简单了，于是现在YYC和nayC在玩一种新的猜拳游戏。

游戏分为每轮进行，每轮游戏共有n局石头剪刀布的游戏。一局若分出胜负则胜者得1分，平局双方都不得分。n局结束后，得分高者赢得此轮的胜利。

但是只有1轮的话还是太无聊了，于是他们又加强了游戏任意时刻如果nayC比YYC多赢m1轮，则nayC获胜；如果YYC比nayC多赢m2轮，则YYC获胜。

为了表现自己的绅士风度，YYC把他每一局出石头，布，剪刀的概率告诉了妹子，分别为ri,pi,si，而且对于不同的两轮中的同一局YYC出石头剪刀布的概率是相等的，现在YYC想问你他的妹子的赢的最大概率是多少？因为nayC开心就好。

有多组数据。

输入

对于每组数据：

第一行包含三个正整数n,m1,m2，含义如题目描述。

接下来n行，每行三个整数ri，pi，si分别表示YYC该局出石头，布，剪刀的概率的百分数，保证ri +pi +si =100

输入数据以0 0 0结束

输出

对于每组数据输出一行一个实数表示nayC获胜的最大概率，四舍五入保留5位小数。

样例

Input:

output:

1.00000
0.85224

分析

可以看到每一轮是独立的，我们先考虑最后的答案

设\(f_i\)为当前nayC赢了\(i\)局的胜率，假设每次都一直玩到分出胜负，每一轮的胜率为\(x\),败率为\(y\)，则

\(f_i=\left\{\begin{aligned} 1 ,&& i=m1\\0 ,&& i=-m2\\\frac{y}{x+y}f_{i-1}+\frac{x}{x+y}f_{i+1} && i\in (-m2,m1)\end{aligned} \right.\)

可以通过迭代/高斯消元得到，同时还能发现答案其实要求\(\frac{x}{x+y}\)最大

由于这是一个分数形式，前面不能直接存在\(dp\)值里取\(max\)，所以我们考虑用01规划

设\(\frac{x}{x+y} \ge t,x\ge t(x+y)\)可以看到是一个线性表达式的样子，可以直接乘上系数转移，所以我们二分\(t\)，\(dp\)前面的n轮，枚举每一轮取什么方案，得到最大的\(x-t(x+y)\)，然后进行下一步迭代

tips:精度不需要太高。。。

const int N=1010;

bool be;
int n,m1,m2;
int w[N][3];
double dp[N][N*2];
const double eps=1e-8; // 精度不需要太高
double fx[N],f[N];

int Check(double mid){
	rep(i,0,n*2) {
		if(i<n) dp[0][i]=-mid;
		if(i>n) dp[0][i]=1-mid;
		if(i==n) dp[0][i]=0;
	}
	rep(i,1,n) rep(j,i,n*2-i) {
		dp[i][j]=-1e9;
		rep(k,0,2) cmax(dp[i][j],(dp[i-1][j]*w[i][k]+dp[i-1][j-1]*w[i][(k+1)%3]+dp[i-1][j+1]*w[i][(k+2)%3])/100);
	}
	return dp[n][n]>eps;
}

bool ed;
int main(){
	while(~scanf("%d%d%d",&n,&m1,&m2) && (n||m1||m2)) {
		rep(i,1,n) rep(j,0,2) w[i][j]=rd();
		rep(i,1,n/2) rep(j,0,2) swap(w[i][j],w[n-i+1][j]); // 注意一下顺序
		double l=0,r=1;
		while(r-l>eps) {
			double mid=(l+r)/2;
			if(Check(mid)) l=mid;
			else r=mid;
		}
		double x=l,y=1-x;
		int m=m1+m2;// 迭代f[i],这里是f[m1-i]
		fx[m]=0;
		drep(i,m-1,1) fx[i]=x/(1-y*fx[i+1]);
		f[0]=1;
		rep(i,1,m) f[i]=f[i-1]*fx[i];
		printf("%.5lf\n",f[m1]);
	}
}