本文主要是介绍codeforces#253 div.2 PD，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这场CF挺有意思的，在做B的时候卡住了，本想放弃去看球赛了，但是一咬牙坚持下来，没想到最后还紫了（虽然又是要div1一日游的节奏T_T）
感觉这种DP方法挺有意思的（一看就是菜鸟的思路T_T），因此还是总结一下~
首先我将dp[i][j]定义为在前i个人中选出j个人最大的期望,那么就转化成了一种很基础的dp模型
但是问题的关键在于如何找到dp的转移关系呢?
那么也应该和对应模型是相同的
即在考虑第i个人的时候,dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+val[i])
这个自然没有问题,但是其中的val[i]应该如何表示呢?
因此我再多记录一个值,就是在对应选择方案下,一个问题都想不出来的期望（即dp[i][j][0]）
为什么记录它?因为假设选出来的j个人中的想出一个问题的概率分别为p[1],……p[j]
那么dp[i][j][1]=p[1]*(1-p[2])*……*(1-p[j-1])*(1-p[j])+(1-p[1])*p[2]*……*(1-p[j])+……+(1-p[1])*(1-p[2])*……*p[j];
将前j-1项提出公因式(1-p[j])，故得dp[i][j][1]=dp[i-1][j-1][1]*(1-p[j])+dp[i][j][0]*p[j];
基本上大功告成啦~成功推出转移方程
再来说说为什么要这样记录dp[i][j][0]，因为从关系式可以得到，我们需要的是在dp[i][j][1]最大时对应的选择方案（即选择哪一些人来想问题），因此在每一次将人加入选择方案的时候，同时也需要维护一下dp[i][j][0]，即再乘上本次选择的那个人的想不出问题的期望，这下真的大功告成了
于是就有了以下代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int SIZEN=1005;
double dp[SIZEN][SIZEN][2];
int main()
{int i,j;int n;double p[SIZEN];scanf("%d",&n);for(i=1;i<=n;i++) scanf("%lf",&p[i]);for(i=0;i<=n;i++){dp[i][0][0]=1;dp[i][0][1]=0;}for(i=1;i<=n;i++){for(j=1;j<i;j++){double tmp=dp[i-1][j-1][1]*(1-p[i])+dp[i-1][j-1][0]*p[i];if(dp[i-1][j][1]>tmp){dp[i][j][1]=dp[i-1][j][1];dp[i][j][0]=dp[i-1][j][0];}else{dp[i][j][1]=tmp;dp[i][j][0]=dp[i-1][j-1][0]*(1-p[i]);}}dp[i][i][1]=dp[i-1][i-1][1]*(1-p[i])+dp[i-1][i-1][0]*p[i];dp[i][i][0]=dp[i-1][i-1][0]*(1-p[i]);}double ans=0;for(i=1;i<=n;i++){for(j=1;j<=i;j++)ans=max(dp[i][j][1],ans);}printf("%.10lf\n",ans);return 0;
}这篇关于codeforces#253 div.2 PD的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
