HDU-5045 Contest 状态压缩DP求期望

2015-07-20 17:35:59 · 作者: · 浏览: 3

N个人,M道题,M个小时,每个人做一道题需要1个小时。给出一个N*M的矩阵代表每个人做对每道题的概率。然后要求在任何时刻,任意两个人的敲题时间差不能大于1,也就是说,m道题要分成多段长度为n的最优排列,n为10,2^10=1024 1024*1000 状压即可。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          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<