http://acm.hdu.edu.cn/showproblem.php?pid=5045
题意：n个学生m道题，一个n*m的矩阵代表第n个学生解第m题AC的概率，任意两学生做题数差距不能大于1，问AC所有题目概率的最大值
由于限制条件，所以一定是以n个学生为单位，一轮一轮的做题，直到做m题为止，这样题目就转化为了一个状态压缩dp，当状态为(1<<n)-1的时候清空状态
dp[i][j]表示AC 前i道题目状态为j的最大值
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <algorithm>
using namespace std ;
typedef __int64 ll ;
double dp[][] ;//
double p[][] ; int n,m ; int main()
{
int T ;
scanf("%d",&T) ;
for(int cas= ;cas<=T ;cas++)
{
scanf("%d%d",&n,&m) ;
for(int i= ;i<n ;i++)
{
for(int j= ;j<m ;j++)
scanf("%lf",&p[i][j]) ;
}
for(int i= ;i< ;i++)
for(int j= ;j< ;j++)
dp[i][j]=-1.0 ;
dp[][]=0.0 ;
int sm=(<<n)- ;
for(int i= ;i<m ;i++)
{
for(int s= ;s<=sm ;s++)
{
if(dp[i][s]<0.0)continue ;
int st= ;
for(int j= ;j<n ;j++)
{
if(!((<<j)&s))
{
st=(<<j)|s ;
if(st==sm)st= ;
dp[i+][st]=max(dp[i+][st],dp[i][s]+p[j][i]) ;
}
}
}
}
double ans=0.0 ;
for(int i= ;i<=sm ;i++)
ans=max(ans,dp[m][i]) ;
printf("Case #%d: %.5lf\n",cas,ans) ;
}
return ;
}