BZOJ 4008 亚瑟王(概率DP 奥妙重重)

题意

中文题面，就不解释了

分析

显然这道题直接求期望太麻烦，想想转化问题（这转化太神了）。

定义f(i,j)f(i,j)f(i,j)表示第iii张卡总共被经过jjj次的概率，有转移方程式

f(i,j)=f(i−1,j)∗(1−pi−1)j+f(i−1,j+1)∗(1−(1−pi−1)j+1)\large 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,j)=f(i−1,j)∗(1−pi−1)j+f(i−1,j+1)∗(1−(1−pi−1)j+1)最终答案就是

∑i=1n∑j=1rf(i,j)∗(1−(1−p[i])j)∗di\large \sum_{i=1}^n\sum_{j=1}^rf(i,j)*(1-(1-p[i])^j)*d_ii=1∑nj=1∑rf(i,j)∗(1−(1−p[i])j)∗di

−.−-.-−.−

AC CODE

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 250;

const int MAXM = 150;

double p[MAXN], d[MAXN], f[MAXN][MAXM], mul[MAXN][MAXM];

int main () {

	int T, n, m;

	scanf("%d", &T);

	while(T--) {

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

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

			scanf("%lf%lf", &p[i], &d[i]);

			mul[i][0] = 1;

			for(int j = 1; j <= m; ++j)

				mul[i][j] = mul[i][j-1] * (1-p[i]);

		}

		memset(f, 0, sizeof f);

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

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

			for(int j = m; j >= 1; --j) {

				if(!(i == 1 && j == m))

					f[i][j] = f[i-1][j] * mul[i-1][j] + f[i-1][j+1] * (1-mul[i-1][j+1]);

				ans += f[i][j] * (1-mul[i][j]) * d[i];

			}

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

	}

}

TIP:预处理幂快的多

巴特西

BZOJ 4008 亚瑟王(概率DP 奥妙重重)

题意

分析

AC CODE

最新文章

热门文章