ZOJ3777 Problem Arrangement {DP}【状态压缩DP】

题意

    给定一个$n\ast n$的矩阵$p$，$p[i][j]$表示第$i$个物品放在第$j$个位置产生的快乐值。如果产生总快乐值大于等于$m$，则这个顺序是可以接受的。问可接受的顺序与总顺序的比（化为最简形式）。如果没有可接受的顺序，则输出$"Nosolution"$。

题解

    $dp[i][j]$表示第$i$种情况快乐值达到$j$的次数。     直接状压套路枚举$0$到$(1<<n)-1$的每种状态，再暴力枚举$0$到$m$的每个快乐值进行递推即可。     状态转移方程：$dp[i+(1<<(j-1))][k+p[num+1][j]]+=dp[i][k];$

#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <functional> #include <iostream> #include <map> #include <queue> #include <stack> #include <string> #include <unordered_map> #include <vector> #define lowbit(x) ((x) & -(x)) using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 1e6 + 10, NN = 2e2 + 10, INF = 0x3f3f3f3f, LEN = 20; const ll MOD = 1e9 + 7; const ull seed = 31; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * f; } int n, m, total; int p[NN][NN], dp[1 << 12][600], fav[NN]; void init() { fav[0] = 1; for (int i = 1; i <= 12; i++) fav[i] = fav[i - 1] * i; memset(dp, 0, sizeof dp); dp[0][0] = 1; } int gcd(int x, int y) { return x == 0 ? y : gcd(y % x, x); } int main() { int T; scanf("%d", &T); while (T--) { init(); scanf("%d%d", &n, &m); total = 1 << n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) scanf("%d", &p[i][j]); for (int i = 0; i < total; i++) { int num = 0; // num表示已经确定了前num行选了哪几列，也就是已经选了num行 for (int j = 1; j <= n; j++) //计算num if (i & (1 << (j - 1))) ++num; for (int j = 1; j <= n; j++) { if (i & (1 << (j - 1))) //如果已经选过则直接continue continue; for (int k = 0; k <= m; k++) { if (k + p[num + 1][j] >= m) //若大于等于m则直接将状态转移到m上 dp[i + (1 << (j - 1))][m] += dp[i][k]; else dp[i + (1 << (j - 1))][k + p[num + 1][j]] += dp[i][k]; } } } if (!dp[total - 1][m]) printf("No solution\n"); else { int temp = gcd(fav[n], dp[total - 1][m]); printf("%d/%d\n", fav[n] / temp, dp[total - 1][m] / temp); } } return 0; }