学步园

这一题开始没有注意 at any time，题目半天没看懂啥意思。 {1,1,3,2,3}是illegal的原因是在第三个同学做题时，1已经比2多做两题了。所以为了满足任意时刻做题数目不超过1，只能一轮一轮的做，就是[1,n]的时间段里，每个人都要做一题，就是1~n的全排列。

蒟蒻表示直接对M/N组每组做了N次，再对M%N做一次。但是大神们的另一种做法要方便很多，点击打开链接

dp[i][j]，i表示当前学生的状态，用二进制数表示，每一位是1就表示这个学生做过题了，j表示做到了第几题。

这一题WA了几次==是因为状态转移到dp[(1<<N)-1][j]时，这一轮结束，下一轮的状态是从x=0开始的，所以前一轮x=(1<<N)-1时要将x=0。果真样例都是骗人的=。=

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
using namespace std;

//hdu 5045
int T;
int N;
int M;
double p[15][1010];
double dp[1<<11][1010];//dp[i][j] means the maximum probability, j is the number of submitted problems and i is the status of students
double ans;
void run()
{
    memset(dp,0,sizeof(dp));
    ans=0;
    dp[0][0]=0;
   // for(int i=0;i<N;i++) dp[1<<i][1]=p[i+1][1];
    int round=M/N;
    int remain=M%N;
  //  cout<<round<<" "<<remain<<endl;
    for(int r=0;r<round;r++)
    {
        for(int i=0;i<(1<<N);i++)
        {
            for(int k=0;k<N;k++)
            {
                if(i&(1<<k)) continue;
                int x=i|(1<<k);

                int cnt=0;
                for(int j=0;j<N;j++)
                {
                    if(x&(1<<j))
                    {
                        cnt++;//找出1的个数，代表此时几个人做题，即做了几题
                    }
                }
                if(x==(1<<N)-1) x=0;
            //    cout<<r*N+cnt<<" "<<hex<<x<<" "<<dp[x][r*N+cnt]<<endl;


                dp[x][r*N+cnt]=max(dp[x][r*N+cnt],dp[i][r*N+cnt-1]+p[k+1][r*N+cnt]);//求的是期望值，所以概率之间是相加关系：sum[1*p+0*(1-p)]
              //  cout<<dp[x][r*N+cnt]<<" "<<dp[i][r*N+cnt-1]<<" "<<k+1<<" "<<r*N+cnt<<" "<<hex<<x<<endl;
            }
        }
    }
    //dp[0][round*N]=dp[(1<<N)-1][round*N];
    for(int i=0;i<(1<<N);i++)
    {
        for(int k=0;k<N;k++)
        {
            if(i&(1<<k)) continue;
            int x=i|(1<<k);
            int cnt=0;
            for(int j=0;j<N;j++)
            {
                if(x&(1<<j))
                {
                    cnt++;
                    if(cnt>remain) continue;
                }
            }
             if(x==(1<<N)-1) x=0;
            dp[x][round*N+cnt]=max(dp[x][round*N+cnt],dp[i][round*N+cnt-1]+p[k+1][round*N+cnt]);
          //  cout<<dp[x][round*N+cnt]<<" "<<dp[i][round*N+cnt-1]<<" "<<k+1<<" "<<round*N+cnt<<" "<<hex<<x<<endl;
        }
    }
    for(int i=0;i<(1<<N);i++)
    {
        ans=max(ans,dp[i][M]);
    }
}
int main()
{
    freopen("input.txt","r",stdin);
   // freopen("data.txt","r",stdin);
   // freopen("out1.txt","w",stdout);
   memset(p,0,sizeof(p));
   scanf("%d",&T);
   for(int ca=1;ca<=T;ca++)
   {
       scanf("%d %d",&N,&M);
       for(int i=1;i<=N;i++)
       {
           for(int j=1;j<=M;j++)
           {
               scanf("%lf",&p[i][j]);
           }
       }
       run();
       printf("Case #%d: %.5lf\n",ca,ans);

   }
    return 0;
}