Hdu 5045 Contest (2014 上海Online) (状态压缩dp)

蔚落 2022-08-12 16:03 155阅读 0赞

听说还可以用二分图什么的搞……因为最多只有10个人，所以可以状态压缩。好久没敲状压了，置位的地方敲错一个符号调了半个小时。。。。

由题意可知，对于n个人，那么题目按顺序每n道题分成一组，每组每个人都要做且仅做一题，对于这n个人在这组中是否已经做过一题可以用二进制表示。

dp\[i\]\[j\] 表示做第i题时j状态下的最大期望，j的每一位为0表示本轮他还没有做过题，为1表示本轮做过。

#include <cstdio>
    #include <cstring>
    #include <vector>
    using namespace std;
    #define max(a,b) ((a)>(b)?(a):(b))
    #define pb push_back
    
    const int N=10;
    const int M=1005;
    vector<int> can[15];
    
    int n,m;
    double ans=0;
    
    int limit;  //limit-1为全1
    
    double dp[M][(1<<N)+5];
    double P[N][M];
    
    //计算一个整型数x的二进制中1的个数
    int Cal (int x)
    {
        int cnt=0;
        while (x)
        {
            cnt++;
            x&=(x-1);
        }
        return cnt;
    }
    
    void Init ()
    {
        int i;
        limit=1<<n;
        ans=0;
        for (i=0;i<=n;i++)
            can[i].clear();
        for (int i=0;i<limit;i++)
                can[Cal(i)].push_back(i);
        for (i=0;i<n;i++) //init
        {
            dp[0][1<<i]=P[i][0];
            ans=max(ans,P[i][0]);
        }
    
    
    }
    
    double Deal ()
    {
        int i,j,k,state,lun;
        bool flag=false;
        for (i=1;i<m;i++)
        {
            if (i==m-1) flag=true;
            lun=i%n;  //本轮应有几个1
            if (lun==0)
                for (k=0;k<n;k++)
                    { //dp[i-1][limit-1]必然上轮最大
                        dp[i][1<<k ]=dp[i-1][limit-1]+P[k][i];
                        if (flag) ans=max(ans,dp[i][1<<k]);
                    }
    
            else
            {
                for (int it=0;it<can[lun].size();it++)
                {
                    j=can[lun][it];  //上轮的某个状态
                    for (k=0;k<n;k++)
                    {//此人本轮没做过
                        if ( (j & (1<<k)) == 0 ) //
                        {
                            dp[i][ j| (1<<k) ]=max(dp[i][ j| (1<<k) ],dp[i-1][j]+P[k][i]);
                            if (flag) ans=max(ans,dp[i][ j| (1<<k) ]);
                        }
                    }
                }
    
            }
        }
        return ans;
    }
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        for (int Cas=1;Cas<=T;Cas++)
        {
            scanf("%d%d",&n,&m);
            memset(dp,0,sizeof(dp));
            memset(P,0,sizeof(P));
            int i,j;
            for (i=0;i<n;i++)
                for (j=0;j<m;j++)
                    scanf("%lf",&P[i][j]);
            Init();
            printf("Case #%d: %.5lf\n",Cas,Deal());
        }
        return 0;
    }