Activation HDU - 4089 （概率DP）

kuangbin的博客

强
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2005;

const double eps = 1e-10;

int n, m, k; double p1, p2, p3, p4;

double dp[2][MAXN], c[MAXN], pp[MAXN];

int main() {

	while(~scanf("%d%d%d%lf%lf%lf%lf", &n, &m, &k, &p1, &p2, &p3, &p4)) {

		if(p4 < eps) { puts("0.00000"); continue; }

		double p = p2 / (1 - p1);

		double p31 = p3 / (1 - p1);

		double p41 = p4 / (1 - p1);

		pp[0] = 1;

		for(int i = 1; i <= n; ++i) pp[i] = pp[i-1] * p;

		int now = 0;

		dp[now][1] = p41 / (1 - p);

		c[1] = p41;

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

			now ^= 1;

			for(int j = 2; j <= k; ++j) c[j] = p31 * dp[now^1][j-1] + p41;

			for(int j = k+1; j <= i; ++j) c[j] = p31 * dp[now^1][j-1];

			double tmp = 0;

			for(int j = 1; j <= i; ++j) tmp += pp[i-j] * c[j];

			dp[now][i] = tmp / (1 - pp[i]);

			dp[now][1] = p * dp[now][i] + c[1];

			for(int j = 2; j < i; ++j) dp[now][j] = p * dp[now][j-1] + c[j];

		}

		printf("%.5f\n", dp[now][m]);

	}

}

/*

j==1:    dp[i][1]=p*dp[i][i]+p41;

2<=j<=k: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1]+p41;

k<j<=i:  dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1];

dp[i][j] = dp[i][j-1] * p + c[j]

*/
巴特西

Activation HDU - 4089 （概率DP）

最新文章

热门文章
