首页 > 代码库 > HDU_5045_状态压缩dp
HDU_5045_状态压缩dp
http://acm.hdu.edu.cn/showproblem.php?pid=5045
i从1到m依次更新，dp[i][j]表示更新到i题时，j表示每个人的答题状态，分别用0和1表示（因为每个人相差题数不能超过1），此是为1的人便不能再答题，当所有人都为1的时候，则每个人都置0。
#include<iostream>#include<cstring>#include<cstdio>using namespace std;double a[15][1005],dp[1005][1<<10];int n,m;int main(){ int T; scanf("%d",&T); for(int x = 1;x <= T;x++) { scanf("%d%d",&n,&m); for(int i = 0;i <= m;i++) { for(int j = 0;j < (1<<n);j++) dp[i][j] = -1; } for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) scanf("%lf",&a[i][j]); } 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; for(int k = 1;k <= n;k++) { if((j & (1<<(k-1))) == 0) { int temp = j | (1<<(k-1)); if(temp == (1<<n)-1) temp = 0; dp[i+1][temp] = max(dp[i+1][temp],dp[i][j]+a[k][i+1]); } } } } double ans = -1; for(int i = 0;i < (1<<n);i++) ans = max(ans,dp[m][i]); printf("Case #%d: %.5f\n",x,ans); } return 0;}
HDU_5045_状态压缩dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。