首页 > 编程学习 > LightOJ-1274 Beating the Dataset(期望dp)

LightOJ-1274 Beating the Dataset(期望dp)

发布时间:2022/12/10 17:13:08

I - Beating the Dataset

 LightOJ - 1274 

题意:一个答案文件有n行输出,每行是YES或NO,现在给出文件的总字节数s,YES占3字节,NO占2字节。
要求你输出1个文件,且第一行一定是NO,接下来第i行的内容是答案文件第i-1行的内容,问输出正确行数的期望


题解:期望dp,用逆推。dp[i][j][k]表示当前状态为第i行,已经输出了j个YES,这一行要输出YES(0)/NO(1)
因此可以得出,①如果第i要输出YES,那么i+1行如果输出NO,则i的期望值为i+1的期望值加上+1再乘以输出NO的概率;i+1行如果输出YES,则i的期望值为i+1的期望值乘以输出YES的概率。②如果第i行要输出NO,做法和①相同
递推关系式为dp[i][j][0]=dp[i+1][j+1][0]*p1+(dp[i+1][j][1]+1)*p2
                      dp[i][j][1]=(dp[i+1][j+1][0]+1*p1)*p1+dp[i+1][j][1]*p2
因为不能开5000*5000*2的数组,想到第i位只与第i+1位有关,第一维可以滚动。

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
const int MX = 5e3 + 5;
double dp[2][MX][2];
int main() {int n, s, T;//  freopen ("in.txt", "r", stdin);scanf ("%d", &T);for (int cas = 1; cas <= T; cas++) {scanf ("%d%d", &n, &s);int yes = s - 2 * n;int no = n - yes;memset (dp, 0, sizeof (dp));double ans = 0;for (int i = n - 1; i >= 0; i--) {int ret = n - i, now = i % 2, nxt = (i + 1) % 2;int Max = min (i, yes), Min = max (0, i - no);     //前i个文件中yes的个数为[Min,Max]memset (dp[now], 0, sizeof (dp[now]));for (int j = Min; j <= Max; j++) {double p1 = 1.0 * (yes - j) / ret, p2 = 1.0 * (no - (i - j)) / ret;dp[now][j][0] = dp[nxt][j + 1][0] * p1 + (dp[nxt][j][1] + 1) * p2;dp[now][j][1] = (dp[nxt][j + 1][0] + 1) * p1 +  dp[nxt][j][1] * p2;}}printf ("Case %d: %.7f\n", cas, dp[0][0][0]);//第一行只能输出YES}return 0;
}




本文链接:https://www.ngui.cc/el/2314503.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000