解题思路
不难想到用 $dp[i][j]$ 表示放第 $i$ 个题时趣味值为 $j$ 的方案数,然而有一个问题是不好表示前面 $i-1$ 个都选了哪些。因此这里需要用状态压缩 DP(一看题目数量那么小就应该试图往状压那边想了),把我们的 dp 数组中的第一维表示为一种题目选择方案(按二进制压缩成一个数存储),然后就很容易写出转移方程(其中 $i$ 表示当前遍历到的状态,$j$ 和 $k$ 分别为 $[1, n]$ 及 $[0, m]$ 的循环,$cnt$ 为当前状态下的已选题目数量):
$$dp[i+2^{j-1}][min(k+a[cnt+1][j], m)] += dp[i][k]$$
参考代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1<<12][501];
int f[13], a[13][13];
int GCD(int a, int b) {
return b ? GCD(b, a%b) : a;
}
int main(int argc, char const *argv[]) {
int t, n, m;
scanf("%d", &t);
f[0] = 1;
for(int i=1; i<=12; ++i) {
f[i] = f[i-1]*i;
}
while(t--) {
scanf("%d %d", &n, &m);
for(int i=1; i<=n; ++i) {
for(int j=1; j<=n; ++j) {
scanf("%d", &a[i][j]);
}
}
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for(int i=0; i<(1<<n); ++i) {
int cnt = 0;
for(int j=1; j<=n; ++j) {
if(i & (1<<(j-1))) cnt++;
}
for(int j=1; j<=n; ++j) {
if(i & (1<<(j-1))) continue;
for(int k=0; k<=m; ++k) {
dp[i+(1<<(j-1))][min(k+a[cnt+1][j], m)] += dp[i][k];
}
}
}
if(dp[(1<<n)-1][m] == 0) printf("No solution\n");
else {
int gcd = GCD(f[n], dp[(1<<n)-1][m]);
printf("%d/%d\n", f[n]/gcd, dp[(1<<n)-1][m]/gcd);
}
}
return 0;
}
还不快抢沙发