HDU-5045 Contest 状态压缩DP求期望
来源：程序员人生 发布时间：2014-10-14 00:18:57 阅读次数：3179次
N个人，M道题，M个小时，每个人做一道题需要1个小时。给出一个N*M的矩阵代表每个人做对每道题的概率。然后要求在任何时刻，任意两个人的敲题时间差不能大于1，也就是说，m道题要分成多段长度为n的最优排列，n为10，2^10=1024 1024*1000 状压即可。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
double ans;
double p[1111][1111];
double dp[1111][1111];
int main()
{
int t;
int cas=1;
scanf("%d",&t);
while(t--)
{
for(int i=0;i<=1024;i++)
{
for(int j=0;j<=1000;j++)
{
dp[i][j]=-1;
}
}
ans=-1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%lf",&p[i][j]);
}
}
int s=(1<<n)-1;//N个全部选过了
dp[0][0]=0;
for(int j=1;j<=m;j++)
{
for(int i=0;i<s;i++)
{
for(int k=1;k<=n;k++)
{
int temp=1<<(k-1);//选到第i个人的时候
if(dp[i][j-1]<0)
{
continue;
}
if(temp&i)//这个人已经被选过
{
continue;
}
int s1=i|temp;//把这个人标记为选过
if(s1==s)//因为时间只差不能超过1，因此是多段n的排列，然后从0开始
{
s1=0;
}
dp[s1][j]=max(dp[s1][j],dp[i][j-1]+p[k][j]);
if(j==m)
{
ans=max(ans,dp[s1][j]);
}
}
}
}
printf("Case #%d: %.5f
",cas++,ans);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
