博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[ACM] hdu 5045 Contest (减少国家Dp)
阅读量:5827 次
发布时间:2019-06-18

本文共 3100 字,大约阅读时间需要 10 分钟。

Contest

Problem Description
In the ACM International Collegiate Programming Contest, each team consist of three students. And the teams are given 5 hours to solve between 8 and 12 programming problems.
On Mars, there is programming contest, too. Each team consist of N students. The teams are given M hours to solve M programming problems. Each team can use only one computer, but they can’t cooperate to solve a problem. At the beginning of the ith hour, they will get the ith programming problem. They must choose a student to solve this problem and others go out to have a rest. The chosen student will spend an hour time to program this problem. At the end of this hour, he must submit his program. This program is then run on test data and can’t modify any more.
Now, you have to help a team to find a strategy to maximize the expected number of correctly solved problems.
For each problem, each student has a certain probability that correct solve. If the i
th student solve the j
th problem, the probability of correct solve is P
ij .
At any time, the different between any two students’ programming time is not more than 1 hour. For example, if there are 3 students and there are 5 problems. The strategy {1,2,3,1,2}, {1,3,2,2,3} or {2,1,3,3,1} are all legal. But {1,1,3,2,3},{3,1,3,1,2} and {1,2,3,1,1} are all illegal.
You should find a strategy to maximize the expected number of correctly solved problems, if you have know all probability
 
Input
The first line of the input is T (1 ≤ T ≤ 20), which stands for the number of test cases you need to solve.
The first line of each case contains two integers N ,M (1 ≤ N ≤ 10,1 ≤ M ≤ 1000),denoting the number of students and programming problem, respectively.
The next N lines, each lines contains M real numbers between 0 and 1 , the j
th number in the i
th line is P
ij .
 
Output
For each test case, print a line “Case #t: ”(without quotes, t means the index of the test case) at the beginning. Then a single real number means the maximal expected number of correctly solved problems if this team follow the best strategy, to five digits after the decimal point. Look at the output for sample input for details.
 
Sample Input
 
1 2 3 0.6 0.3 0.4 0.3 0.7 0.9
 
Sample Output
 
Case #1: 2.20000
 
Source
解题思路:

题意为有n个学生,m道题,已知每位学生对每一个题都有一个答对的可能性,要求一道题目仅仅能一个学生做。一个学生能够做多道。 且随意两个学生之间做的题目之差不能超过1,问m道题所有答对的最大可能性为多少。

n最大为10。所以最多有 0~(2的10次方-1)种状态,每一位代表一个学生。1表示答题。0表示不答题。

当dp[ i ] [ j ]代表前 i  道题,状态为 j 的所有答对最大可能性。状态为j,也就是二进制里面包含i个1,由于要选i个人答题。

比方 dp[ 2 ][ 4],  4 可能是1001 1100 0011  0101等。仅仅要包含2个1就能够。 n<=m的时候

状态转移方程为:  dp [  i +1 ]  [ j ]= max(dp[i+1][j], dp[i-1][ s] + p[ k ][ i ] ) s是一个状态,p[k][i]表示第k个人答对第i道题的可能性

从已知状态推未知状态。

n>m时。由于随意两个学生做的题目仅仅差不能超过1,所以 当全部学生都答过一道题以后,状态要从0開始, dp[i][ (1<<n)-1]已知。也就是dp[i][0]已知

參考:http://www.2cto.com/kf/201409/338936.html

代码:

#include 
#include
#include
using namespace std;const int Max=(1<<10)+1;double dp[1001][Max];//代表前i道题,状态为j做出来题目的最大期望double p[11][1001];int n,m;int s;//最大状态double solve(){ double ans=-1.0; dp[0][0]=0; for(int i=0;i

版权声明:本文博客原创文章。博客,未经同意,不得转载。

你可能感兴趣的文章
mysql root密码重置
查看>>
33蛇形填数
查看>>
我为Net狂 ~ 社交平台系列小集合!
查看>>
Windows API一日一练(66)CreateWaitableTimer和SetWaitableTimer函数
查看>>
中秋节
查看>>
选择排序
查看>>
wpf datagrid 遍历行
查看>>
SQL Server 数据库的数据和日志空间信息
查看>>
Go语言的for循环
查看>>
前端基础之JavaScript
查看>>
ThreadLocal
查看>>
自己动手做个智能小车(6)
查看>>
2018.7.9练习
查看>>
自己遇到的,曾未知道的知识点
查看>>
P1382 楼房 set用法小结
查看>>
分类器性能度量
查看>>
Es学习第七课, term、terms、match等基本查询语法
查看>>
java 解析http返回xml数据
查看>>
windows 环境下切换 python2 与 pythone3 以及常用命令
查看>>
HashMap和Hashtable的差别
查看>>