题意
某场比赛有M道问题,T支队伍,和数字N给出每支队伍解决每道问题的概率。 问这场比赛满足下面两个条件的概率
1.每支队伍至少做出一道题
2.冠军队至少做出N道题。
分析
条件2是不是可以转化为 至少有一支队做出N道及以上道题。
这个题主要是概率,其次才是dp,而且好像不算概率DP。
我们来倒推一下。
设p2为每支队伍做出来的题数都在(1-N-1)的概率。p1为每只队伍至少做出来一道题的概率。那么答案就是p1-p2。
然后我们再来想怎么求p1和p2。设s[i][j]为第i支队伍做出来题数小于等于j的概率。那么
p1=(1-s[1][0])*(1-s[2][0])*...*(1-s[T][0]).
p2=(s[1][N-1]-s[1][0])*(s[2][N-1]-s[2][0])*...*(s[T][N-1]-s[T][0])。
然后再往前推。s[i][j]该怎么求?
我们发现队伍与队伍之间没有关系,于是我们可以每支队伍都通过dp求解。对于每支队伍k
我们令f[i][j]为前i个问题中做出来j个题的概率 f[i][j]=f[i-1][j]*(1-P[k][j])+f[i-1][j-1]*P[k][j];
然后 s[k][j]=sum(f[M][l])(0<=l<=j)
就是这个样子。
这个题的DP是最基础的,但是概率那里我觉得不是特别好想。。(可能因为我菜吧···)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
const int maxn=+;
const int maxm=;
int M,T,N;
double P[maxn][maxm];
double f[maxm][maxm],s[maxn][maxm];
int main(){
while(scanf("%d%d%d",&M,&T,&N)!=EOF&&(M||T||N)){
memset(P,,sizeof(P));
for(int i=;i<=T;i++){
for(int j=;j<=M;j++){
scanf("%lf",&P[i][j]);
}
memset(f,,sizeof(f));
f[][]=1.0;
for(int j=;j<=M;j++){
for(int k=;k<=j;k++){
if(k==)
f[j][k]=f[j-][k]*(-P[i][j]);
else
f[j][k]=f[j-][k-]*P[i][j]+f[j-][k]*(-P[i][j]);
}
}
double sum=;
for(int j=;j<=M;j++){
sum+=f[M][j];
s[i][j]=sum;
}
}
double p1,p2;
p1=p2=1.0;
for(int i=;i<=T;i++){
p1*=(-s[i][]);
}
for(int i=;i<=T;i++){
p2*=(s[i][N-]-s[i][]);
}
double ans=p1-p2;
printf("%.3f\n",ans);
}
return ;
}
【POJ2151】Check the difficulty of problems的更多相关文章
-
【poj2151】 Check the difficulty of problems
http://poj.org/problem?id=2151 (题目链接) 题意 T支队伍,一共M道题,第i支队伍解出第j道题的概率为p[i][j].问每支队伍至少解出1道题并且解题最多的的队伍至少解 ...
-
【POJ】【2151】Check the difficulty of problems
概率DP kuangbin总结中的第8题 一开始题目看错导致想转移方程想错了……想成f[i][j]表示前 i 个队伍中最多的做出来 j 道题的概率……sigh 看了下题解……其实是对于每个队伍 i 单 ...
-
【POJ】2151:Check the difficulty of problems【概率DP】
Check the difficulty of problems Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 8903 ...
-
POJ 2151 Check the difficulty of problems
以前做过的题目了....补集+DP Check the difficulty of problems Time Limit: 2000MS Memory Limit: 65536K ...
-
Check the difficulty of problems
Check the difficulty of problems Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 5830 Acc ...
-
Check the difficulty of problems(POJ 2151)
Check the difficulty of problems Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 5457 ...
-
POJ 2151 Check the difficulty of problems (动态规划-可能DP)
Check the difficulty of problems Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 4522 ...
-
POJ 2151 Check the difficulty of problems 概率dp+01背包
题目链接: http://poj.org/problem?id=2151 Check the difficulty of problems Time Limit: 2000MSMemory Limit ...
-
[ACM] POJ 2151 Check the difficulty of problems (概率+DP)
Check the difficulty of problems Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 4748 ...
随机推荐
-
ASP.NET MVC Dropdownlist
本文介绍如何在网页里显示DropDownList. Step 1: 在Control里面添加方法 public ActionResult ShowDropDownList() { return Vie ...
-
sqlserver重命名字段名称
EXEC sp_rename 'S2BASE_PRODUCT.[PRODUCT_ID]','TABTYPE_ID','COLUMN';
-
GDI+基础(1)
转载:http://www.cnblogs.com/peterzb/archive/2009/07/19/1526555.html System.Drawing 命名空间提供了对 GDI+ 基本图形功 ...
-
在VirtualBox下安装CentOS教程(截图版)
http://blog.csdn.net/kobe_lzq/article/details/7894718 使用的软件: VirtualBox 4.1.2 CentOS 5.6 x86_64 刻录的 ...
-
iOS推送服务细节回顾
iOS推送服务细节回顾 之前在做推送功能时候,就总结过一系列证书的制作,OC代码实现和服务器搭建等经验.又过了一段时间了,前前后后对推送服务做了多次的完善和优化,有iOS客户端的,还有本地服务器端的. ...
-
重装系统之后Hexo快速配置
安装准备软件 Node.js Git 打开 Git Bash hexo文件夹,右键: 配置SSH Keys 检查SSH keys设置,看一下电脑现有的ssh key cd ~/. ssh 检查本机的s ...
-
一个简单的分布式session框架
该代码只是用来学习原理的,有很多不完善之处. 代码: git@github.com:sicw/EasySpringSession.git 一. 整体设置 1. 实现Filter,封装新的reques ...
-
Linear Regression with machine learning methods
Ha, it's English time, let's spend a few minutes to learn a simple machine learning example in a sim ...
-
QT | 一些学习心得
1. 如何使控件随着窗口大小变化而自动填充? 选中控件中最外层的那个控件,如centralWidget(不要去选中内部的小控件,这样能够保证内部的相对位置) 然后对centralWidget选择布局方 ...
-
奇葩问题 eclipse中DDMS的LOGcat只有一列level
http://*.com/questions/25010393/eclipse-logcat-shows-only-the-first-letter-from-each-mes ...