【bzoj4008】 HNOI2015

http://www.lydsy.com/JudgeOnline/problem.php?id=4008 (题目链接)

题意

　　给出n个技能，每个技能按顺序有p[i]的可能性释放，可以造成d[i]的伤害。每一轮游戏只能发动一个技能，问r轮游戏期望造成的伤害。

Solution

　　刚了半个下午的dp，然而Wa了又调，调了又Wa，发现整个dp都是萎的，然后删了重写。。。无奈，看了题解。

　　http://blog.csdn.net/vmurder/article/details/46461649

　　get了求期望的新姿势。。。$${ f_{i,j} = f_{i-1,j} × (1 - p_{i-1})^j + f_{i-1,j+1}×(1-(1-p_{i-1})^{j+1})}$$

　　其中${f_{i-1,j} × (1 - p_{i-1})^j}$表示第${i-1}$张技能牌被所有机会跳过。

　　其中${f_{i-1,j+1}×(1-(1-p_{i-1})^{j+1})}$表示第${i-1}$张技能牌被其中一个机会选中，逆向思考，即1-被所有机会跳过的概率。

　　那么第${i}$张技能牌发动的概率是多少呢？显然：${P_i=\sum_{j=1}^rf_{i,j}×(1-(1-p_{i})^j)}$

代码

// bzoj4008

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 1<<30

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=500;

int d[maxn],n,r;

double p[maxn],f[maxn][maxn];

double power(double a,int b) {

	double res=1;

	while (b) {

		if (b&1) res*=a;

		b>>=1;a*=a;

	}

	return res;

}

int main() {

	int T;scanf("%d",&T);

	while (T--) {

		memset(f,0,sizeof(f));

		scanf("%d%d",&n,&r);

		for (int i=1;i<=n;i++) scanf("%lf%d",&p[i],&d[i]);

		f[0][r]=1;double ans=0;

		for (int i=1;i<=n;i++)

			for (int j=1;j<=r;j++) {

				f[i][j]=f[i-1][j]*power(1-p[i-1],j)+f[i-1][j+1]*(1-power(1-p[i-1],j+1));

				ans+=f[i][j]*(1-power(1-p[i],j))*d[i];

			}

		printf("%.10lf\n",ans);

	}

	return 0;

}

巴特西

【bzoj4008】 HNOI2015—亚瑟王

题意

Solution

代码

最新文章

热门文章