首页 > 代码库 > ZOJ 3777 Problem Arrangement(状压DP)

ZOJ 3777 Problem Arrangement(状压DP)

2024-07-25 09:53:40   227人阅读

题目链接 ： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5264

//今年省赛的题目，比赛的时候知道是状压却一直没搞出，直到最后。虽然赛后知道做法，也一直没做的，最近想不开就来做了 - -， 顺便用了下快速枚举k-子集。

恩， 做法么就是开dp[i][j] i已经选过了的题目的一个集合，j表示的是获得了j分，然后就可以直接做了。。（但是好像说会T或者卡空间，我的做法是快速枚举k-子集，这个东西可以看下watashi翻译的《挑战编程竞赛》的p157。。 汗

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 //#include <cmath> 6  7 using namespace std; 8  9 int P[15][15];10 int dp[1<<12][505];11 int n, m;12 13 int main() {14     int T;15     scanf("%d", &T);16     for (int cas = 1; cas <= T; cas++) {17         scanf("%d%d", &n, &m);18         for (int i = 1; i <= n; i++) {19             for (int j = 1; j <= n; j++) scanf("%d", &P[i][j]);20         }21         memset(dp, 0, sizeof(dp)); dp[0][0] = 1;22 23         for (int k = 1; k <= n; k++) {24             int comb = (1 << k) - 1;25             while (comb < (1 << n)) {26                 for (int i = 0; i < n; i++) {27                     if (comb >> i & 1) {28                         int add = P[i + 1][k], low = max(0, m-add);29                         for (int j = m; j >= low; j--) dp[comb][m] += dp[comb-(1<<i)][j];30                         for (int j = low - 1; j >= 0; j--) dp[comb][j+add] += dp[comb-(1<<i)][j];31                     }32                 }33                 int x = comb & -comb, y = comb + x;34                 comb = ((comb & ~y) / x >> 1) | y;35             }36         }37         int ret = dp[(1<<n)-1][m];38         if (!ret) puts("No solution");39         else {40             int nex = 1;41             for (int i = 1; i <= n; i++) nex *= i;42             int d = __gcd(ret, nex);43             printf("%d/%d\n", nex/d, ret/d);44         }45     }46     return 0;47 }
View Code

 

ZOJ 3777 Problem Arrangement(状压DP)


联系
我们