首页 > 代码库 > zoj 3777 Problem Arrangement

zoj 3777 Problem Arrangement

2024-07-30 18:33:24   217人阅读

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5264

题意：给出n道题目以及每一道题目不同时间做的兴趣值，让你求出所有做题顺序中兴趣值大于等于m的比例。用一个分数表示。

状压dp。 枚举每一个状态，用二进制表示。dp[i][j]表示第i个题目，兴趣值为j的个数。

转移方程 dp[i|(1<<j)][k+a[num][j]]+=dp[i][k];兴趣值大于m的为 dp[1|(1<<j)][m]+=dp[i][k];

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define LL long long 5 using namespace std; 6  7 int t,n,m; 8 int p[15][15]; 9 int dp[1<<13][1000];10 int f[10000];11 12 LL gcd(LL a,LL b)13 {14     return b==0?a:gcd(b,a%b);15 }16 17 int main()18 {19     scanf("%d",&t);20     f[1]=1;21     for(int i=2; i<=12; i++)22     {23         f[i]=f[i-1]*i;24     }25     while(t--)26     {27         scanf("%d%d",&n,&m);28         memset(dp,0,sizeof(dp));29         for(int i=0; i<n; i++)30         {31             for(int j=0; j<n; j++)32             {33                 scanf("%d",&p[i][j]);34             }35         }36         dp[0][0]=1;37         for(int i=0; i<=(1<<n); i++)38         {39             int num=0;40             for(int j=0; j<n; j++)41             {42                 if(i&(1<<j)) num++;43             }44             for(int j=0; j<n; j++)45             {46                 if(i&(1<<j)) continue;47                 for(int k=0; k<=m; k++)48                 {49                     if(k+p[num][j]>=m)50                     {51                         dp[i|(1<<j)][m]+=dp[i][k];52                     }53                     else54                     {55                         dp[i|(1<<j)][k+p[num][j]]+=dp[i][k];56                     }57                 }58             }59         }60         if(dp[(1<<n)-1][m]==0)61         {62             printf("No solution\n");63         }64         else65         {66             int g=gcd(f[n],dp[(1<<n)-1][m]);67             printf("%d/%d\n",f[n]/g,dp[(1<<n)-1][m]/g);68         }69     }70     return 0;71 }
View Code

 

zoj 3777 Problem Arrangement


联系
我们