HDU - 5045 Contest(DP+狀壓)
來源：程序員人生 發布時間：2014-09-29 12:06:37 閱讀次數：2819次
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 ith student solve the jth problem, the probability of correct solve is Pij .
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 jth number in the ith line is Pij .
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
題意：每個人做題是有概率的，每個做題的序列任意兩個人做題的個數不超過1，求最大的概率。
思路：設dp[i][j]表示前i道題，j的狀態，因為不能超過1，所以每個狀態我們都能用01表示，1表示當前做的題目最大，0表示最小的。例如3232，就表示1010，所以我們就能用1<<10的狀態表示了，每次從0的人開始轉移，因為只有0轉移才能是符合條件的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1100;
double dp[maxn][maxn];
double p[maxn][maxn];
int main() {
int n, m;
int t, cas = 1;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%lf", &p[i][j]);
for (int i = 0; i <= m; i++)
for (int j = 0; j <= (1<<n); j++)
dp[i][j] = -1.0;
dp[0][0] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < (1<<n); j++) {
if (dp[i][j] < 0) continue;
int st;
for (int k = 0; k < n; k++)
if (((1<<k)&j) == 0) {
st = j | (1<<k);
if (st == (1<<n)-1) st = 0;
if (dp[i+1][st] < dp[i][j] + p[k][i])
dp[i+1][st] = dp[i][j] + p[k][i];
}
}
}
double ans = 0;
for (int i = 0; i < (1<<n); i++)
ans = max(ans, dp[m][i]);
printf("Case #%d: %.5lf
", cas++, ans);
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
