2014
03-16

# Passage

Bill is a millionaire. But unfortunately he was trapped in a castle. There are only n passages to go out. For any passage i (1<=i<=n), Pi (0<=Pi<=1) denotes the probability that Bill will escape from this castle safely if he chose this passage. Qi (0<=Qi<=1-Pi) denotes the probability that there is a group of guards in this passage. And Bill should give them one million dollars and go back. Otherwise, he will be killed. The probability of this passage had a dead end is 1-Pi-Qi. In this case Bill has to go back. Whenever he came back, he can choose another passage.
We already know that Bill has M million dollars. Help Bill to find out the probability that he can escape from this castle if he chose the optimal strategy.

The first line contains an integer T (T<=100) indicating the number of test cases.
The first line of each test case contains two integers n (1<=n<=1000) and M (0<=M<=10).
Then n lines follows, each line contains two float number Pi and Qi.

The first line contains an integer T (T<=100) indicating the number of test cases.
The first line of each test case contains two integers n (1<=n<=1000) and M (0<=M<=10).
Then n lines follows, each line contains two float number Pi and Qi.

3
1 10
0.5 0
2 0
0.3 0.4
0.4 0.5
3 0
0.333 0.234
0.353 0.453
0.342 0.532

Case 1: 0.50000
Case 2: 0.43000
Case 3: 0.51458

#include <cmath>
#include <vector>
#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1005;

struct Node{
double pi,qi;
};
Node node[maxn];
bool comp(const Node & t1,const Node & t2)
{
return t1.pi*t2.qi < t2.pi*t1.qi; //ѡ��������ӳ�ȥ/�������� �������ġ�
}
double dp[maxn][13];
int main(int argc,char *argv[])
{
int n,m;
int t,i,j,ncase = 0;
scanf("%d",&t);
while(t --)
{
scanf("%d%d",&n,&m);
for(i = 1;i <= n;i ++)
scanf("%lf%lf",&node[i].pi,&node[i].qi);
sort(node+1,node+n+1,comp);
for(i = 0;i <= m;i ++) dp[1][i] = node[1].pi; //���Ѹ���
//����ͬ 1 - pi - qi
for(i = 2;i <= n;i ++)
{
for(j = 0;j <= m;j ++)
{
dp[i][j] = node[i].pi + (1-node[i].pi-node[i].qi)*dp[i-1][j];
if(j >= 1)
dp[i][j] += node[i].qi*dp[i-1][j-1];
}
}
ncase ++;
printf("Case %d: %.5f\n",ncase,dp[n][m]);
}
return 0;
}

1. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

3. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。