题目背景： czk赫赫有名，为什么呢？因为他参加了超多竞赛，所以认识了无数OIer。而无数OIer也都认识他，为什么呢？因为czk实在是太牛了~ 所以我们经常可以听到OIer之间的典型谈话： 小A：你知道czk吗？ 小B：当然认识啦，就是那个AK了XX竞赛的dadiao啊~ 小A：不止，他还AK了XX竞赛，XX竞赛，XX竞赛…… 那么，czk同学到底巨到什么地步呢？ 世界上总共有N门竞赛，czk同学参加了全部，并且都拿到了保送！！并且还会经常性地虐全场。（其实czk虐场地概率高达200%，但是为了题目需要，只能把czk dadiao写菜10inf倍） 题目描述： 现在有n场竞赛，czk对于不同竞赛有不同的概率虐场。现在czk想知道，他有多少的概率至少虐m次场。 输入格式： 第一行两个用空格隔开的正整数n，m 下面N行，每行一个0~1的实数，第i+1行的实数表示第i个竞赛虐场的概率。 输出格式： 一行一个实数，表示至少虐m次场的概率。实数保留六位小数。 输入样例1： 2 1 1 1 输出样例1： 1.000000 输入样例2： 3 1 0.046921 0.959868 0.008229 输出样例2： 0.962066 说明： 对于100%的数据，满足1≤m≤n≤20
知识点： 概率DP 讲解： 对于这一题首先要知道一些概率的计算公式： 乘法定则： 我们定义三个事件发生的概率为A，B，C，如果A和B同时发生才出现C，那么出现C的概率为A*B 加法定则： 如果A和B任意满足一个都会出现C，那么出现C的概率为A+B 知道了这两个公式之后我们再看一下这题，题目要求至少虐m场的概率，换句话说就是虐m场及以上的概率和，这个也就是加法定则，因为只要是m及以上都可以得到至少虐m场，符合加法定则，所以我们发现如果要计算虐i场的概率的话，要知道两个条件，一个是总共有几场，另一个是虐i场，所以我们可以定义出状态dp[i][j]表示总共i场虐j场，对于状态转移方程，我们假设第i场czk不打算虐场，那么dp[i][j]=dp[i-1][j]*(1-a[i]) 其中a[i]表示第i场czk虐场的概率，而（1-a[i]）表示第i场czk不虐场的概率，对于第i场czk虐场的话，dp[i][j]=dp[i-1][j-1]a[i]，因为上面的两种情况满足加法定则，所以我们可以这么写，dp[i][j]=dp[i-1][j](1-a[i])+dp[i-1][j-1]a[i]，这样状态转移方程就出来了，还有一个要注意，就是我们在DP时当j==0的话只能dp[i-1][j](1-a[i])，如果不特盘会数组越界。 上代码：
#include<iostream> #include<cstdio> using namespace std; double a[40],dp[40][40]; int main() { int n,m; double ans=0; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) scanf("%lf",&a[i]);//读入数据 dp[0][0]=1;//初始化 for(int i=1;i<=n;i++) for(int j=0;j<=i;j++) if(j==0)//特判 dp[i][j]=dp[i-1][j]*(1-a[i]); else dp[i][j]=dp[i-1][j-1]*a[i]+dp[i-1][j]*(1-a[i]);//正常DP for(int i=m;i<=n;i++)//统计答案 ans+=dp[n][i]; printf("%.6f",ans);//输出 return 0; }有不懂的，或者上面没讲清楚的欢迎留言。 祝大家都可以AC。
