HDU_5045_状态压缩dp
2024-09-01 20:08:18
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[][],dp[][<<];
int n,m; int main()
{
int T;
scanf("%d",&T);
for(int x = ;x <= T;x++)
{
scanf("%d%d",&n,&m);
for(int i = ;i <= m;i++)
{
for(int j = ;j < (<<n);j++) dp[i][j] = -;
}
for(int i = ;i <= n;i++)
{
for(int j = ;j <= m;j++) scanf("%lf",&a[i][j]);
}
dp[][] = ;
for(int i = ;i < m;i++)
{
for(int j = ;j < (<<n);j++)
{
if(dp[i][j] < ) continue;
for(int k = ;k <= n;k++)
{
if((j & (<<(k-))) == )
{
int temp = j | (<<(k-));
if(temp == (<<n)-) temp = ;
dp[i+][temp] = max(dp[i+][temp],dp[i][j]+a[k][i+]);
}
}
}
}
double ans = -;
for(int i = ;i < (<<n);i++) ans = max(ans,dp[m][i]);
printf("Case #%d: %.5f\n",x,ans);
}
return ;
}
最新文章
- IOS lib(.a)库冲突解决办法
- poj2115-C Looooops(扩展欧几里德算法)
- JQuery[一] 中如何选中$(this)下面的子元素
- IEEE Floating Point Standard (IEEE754浮点数表示法标准)
- 通过预编译头文件来提高C++ Builder的编译速度
- 用JSON 和 Google 实现全文翻译
- HTML 5 学习 (1)
- LInux 下安装jdk
- Spoken English
- Android从无知到有知——NO.4
- 关于scrapy的piplines
- 【BZOJ4872】分手是祝愿(动态规划,数学期望)
- 关于LINUX里面查找,替换,编辑的一些用法
- 乐学习知选择--我的J2EE技术历程
- Refit在ASP.NET Core中的实践
- 超哥笔记 --nginx入门(6)
- python之路day01--变量
- 《JavaScript 高级程序设计》读书笔记一 简介
- 1006 Tick and Tick
- R 语言安装