ZOJ 3777 Problem Arrangement(状压 DP)解题报告

2017-01-16 2,132 次浏览 解题报告

解题思路

不难想到用 $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;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2017/01/16/zoj-3777.dream

还不快抢沙发

添加新评论