【NOI六连测】[D3T1] 炉石

题目传送门:http://pan.baidu.com/s/1nvKqStz
离线版数据:http://paste.ubuntu.com/18386939/
数据传送门:http://pan.baidu.com/s/1i5fN2IT

首先,没玩过炉石的同学表示很受伤:考试的时候一直以为95颗星就算赢
其次,不会概率DP or 高斯消元的同学表示很受伤:因为要爆零啊!QAQ
好吧,高斯消元不会,所以来说一说lcr用的模拟吧:
设arr[i][j]表示走了k步后,位于当前有i颗星,已经连胜j场这个状态的概率
于是转移一下,再加上P>0.48保证了最多的步数就是1000多的样子
所以我们暴力转移1e5次的样子,基本上其他地方的DP值就为0了。
然后就是NOIP的模拟题水平的代码就可以了! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
哎,概率太弱不对,是完全不会
迟早是要找个时间好好学一学啊!

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100;
const int T = 100000;

double win,lose,arr[MAXN][4],tmp[MAXN][4],ans;
int n;

int main(){
	freopen("hearthstone.in","r",stdin);
	freopen("hearthstone.out","w",stdout);
	scanf("%d%lf",&n,&win);
	lose = 1 - win;
	arr[96-n][0] = 1;
	for (int k=1;k<=T;k++){
		for (int i=0;i<=10;i++){
			tmp[i][0] += arr[i][0]*lose;
			tmp[i][0] += arr[i][1]*lose;
			tmp[i][0] += arr[i][2]*lose;
			tmp[i][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+2][3] += arr[i][2]*win;
			tmp[i+2][3] += arr[i][3]*win;
		}
		for (int i=11;i<=70;i++){
			tmp[i-1][0] += arr[i][0]*lose;
			tmp[i-1][0] += arr[i][1]*lose;
			tmp[i-1][0] += arr[i][2]*lose;
			tmp[i-1][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+2][3] += arr[i][2]*win;
			tmp[i+2][3] += arr[i][3]*win;
		}
		for (int i=71;i<=95;i++){
			tmp[i-1][0] += arr[i][0]*lose;
			tmp[i-1][0] += arr[i][1]*lose;
			tmp[i-1][0] += arr[i][2]*lose;
			tmp[i-1][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+1][3] += arr[i][2]*win;
			tmp[i+1][3] += arr[i][3]*win;
		}
		ans += (tmp[96][0]+tmp[96][1]+tmp[96][2]+tmp[96][3])*k; 
		memcpy(arr,tmp,sizeof(tmp));
		memset(tmp,0,sizeof(tmp));
	}
	printf("%.2lf\n",ans);
	return 0;
} 

发表评论

电子邮件地址不会被公开。 必填项已用*标注