首页 > ACM题库 > HDU-杭电 > HDU 3366-Passage[解题报告]HOJ
2014
03-16

HDU 3366-Passage[解题报告]HOJ

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