hdu 5045 Contest 상태 압축 dp

임의의 시간에 임의의 두 사람의 퀴즈 시간은 1시간을 초과해서는 안 된다.다시 말하면 n문제마다 n명이 한 번씩 돌아가야 한다(n은 인원수).
상태 압축 dp, dp[i][j]는 퀴즈 전 i문제의 퀴즈 인원을 j 상태로 분배할 때의 최대 기대를 나타낸다.

#include <iostream>
#include<stdio.h>
using namespace std;
int n,m;
double p[20][1010],dp[1010][1500],ans;

void init()
{
    for(int i = 0;i <= m;i++)
        for(int j = 0;j <= (1<<n);j++) dp[i][j] = -1;
    dp[0][0] = 0;
}


void work()
{
    init();
    for(int i = 0;i < m;i++) //     
    {
        for(int j = 0;j < 1<<n;j++)//       
        {
            if(dp[i][j]<0)continue;
            for(int k = 0;k < n;k++) //         
            {
                if(((j>>k)&1)==0) //         
                {
                    int tmp = j|(1<<k);
                    if(tmp == (1<<n)-1) tmp = 0;
                    if(dp[i][j]+p[k][i+1] > dp[i+1][tmp])
                    {
                        dp[i+1][tmp] = dp[i][j]+p[k][i+1];
                    }
                }
            }
        }
    }

}

int main()
{
    int t;
    scanf("%d",&t);
    int cas = 1;
    while(t--)
    {
        scanf("%d %d",&n,&m);
        for(int i = 0;i < n;i++) //    0  ，     1  
            for(int j = 1;j <= m;j++) scanf("%lf",&p[i][j]);
        ans = 0;
        work();
        for(int i = 0;i < (1<<n);i++) if(dp[m][i] > ans) ans = dp[m][i];
        printf("Case #%d: %.5lf
",cas++,ans);
    }
    return 0;
}