首页 > 代码库 > hdu5045||2014 ACM/ICPC Asia Regional Shanghai Online【数位dp】
hdu5045||2014 ACM/ICPC Asia Regional Shanghai Online【数位dp】
大意：有n道题m个熊孩子，每个熊孩子对于每个题的正确率是已知的，对于每一道题必须有且只有一个熊孩子去做， 并且在任意时刻任意两个熊孩子的做的题数之差都不能大于等于2
比如有5个题三个熊孩子
那么1 2 3 3 1是合法的
但是12231是不合法的
求的是最大期望
分析：
题目已知熊孩子的数目最多是十个那么我们可以将其压缩成2进制（1024）
dp[i][j]表示对于前i道题，状态为j的最大概率
那么&运算和|运算就能很好的处理这个问题
对于（1<<n - 1) 要将其清空
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 1005; 7 const int maxm = 1 << 11; 8 9 double dp[maxn][maxm];10 double p[15][maxn];11 double max(double x, double y) {12 return x > y ? x : y;13 }14 15 int main() {16 int t, n, m;17 scanf("%d",&t);18 for(int kiss = 1; kiss <= t; kiss++) {19 scanf("%d %d",&n, &m);20 for(int i = 0; i < n; i++) {21 for(int j = 0; j < m; j++) {22 scanf("%lf",&p[i][j]);23 }24 }25 for(int i = 0; i < m; i++) {26 for(int j = 0; j < ( 1 << n ); j++) {27 dp[i][j] = -1.0;28 }29 }30 for(int i = 0; i < n; i++) {31 dp[0][1<<i] = p[i][0];32 }33 for(int i = 1; i < m; i++) {34 for(int j = 0; j < ( 1 << n ); j++) {35 if(dp[i - 1][j] != -1) {36 for(int k = 0; k < n; k++) {37 if((j & (1 << k )) == 0) {38 dp[i][(j|(1 << k))] = max(dp[i][j|(1 << k)], dp[i - 1][j] + p[k][i]);39 }40 }41 }42 }43 if(dp[i][(1 << n) - 1] != -1) {44 dp[i][0] = dp[i][(1 << n) - 1];45 dp[i][(1 << n) - 1] = -1;46 }47 }48 double ans = 0;49 for(int i = 0; i < ( 1 << n ); i++) {50 ans = max(ans, dp[m - 1][i]);51 }52 printf("Case #%d: %.5lf\n", kiss, ans);53 }54 return 0;55 }
hdu5045||2014 ACM/ICPC Asia Regional Shanghai Online【数位dp】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。