WZB's Harem 状压DP

WZBs Harem

https://ac.nowcoder.com/acm/contest/8827/L

状压DP

每一列对于每一行是唯一确定的,这一点契合了状态压缩的特性。

出题人的话:

一道状压 dp。首先不考虑皇后的差异性,把所有皇后当作是一样的,在第 i 行第 k 列安排一位皇后的方案数为 f[i][j|(1<<k)] += f[i][j]((j>>k)&1==0)。因为皇后不可能是一样的,所以最后的结果为 f[n][1<<(n-1)]*(n!)

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
const int maxn = 22;
const int maxm = (1 << 21) + 10;
int n;
int g[maxn][maxn];   //图
int s[maxn][maxm];   // s[x][]表示有x个1的所有状态
int p[maxn];         //行游标
int dp[maxn][maxm];  // n行 m个状态 里有多少个合法情况
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) scanf("%d", &g[i][j]);
    for (int i = 0; i < (1 << n); ++i) {
        //枚举所有长度为n的二进制串,表示一行的可选状态
        int cnt = __builtin_popcount(i);  // i里有多少个1
        s[cnt][++p[cnt]] = i;             // s[x][]表示x个1的所有状态
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (g[i][j]) continue;  //不可选
            for (int k = 1; k <= p[i - 1]; k++) {
                //枚举i-1个1的所有状态:之前选的所有状态
                int pre = s[i - 1][k];  //前面几行可能的选择状态
                if ((pre >> (j - 1)) & 1) continue;
                //不能有同一列 且 不可达此状态 这正是状压的可行性
                int cur = pre | (1 << (j - 1));  //把从右往左第j位置1
                dp[i][cur] = (dp[i][cur] + dp[i - 1][pre]) % MOD;
                // 当前状态
            }
        }
    }
    ll fac = 1;
    for (ll i = 1; i <= n; i++) fac = fac * i % MOD;  //全排列
    printf("%lld\n", fac * dp[n][(1 << n) - 1] % MOD);
    return 0;
}
算法竞赛之路 文章被收录于专栏

整理、记录算法竞赛的好题

全部评论

相关推荐

07-04 21:23
已编辑
东莞城市学院 后端
秋招和春招只收到几个中大厂的笔试,本人比较菜,感觉大厂的笔试太难,算法题不能全部做出来就没过了,但是CVTE和小天才的感觉不是很难,基本上都做出来了,笔试还是挂了。Boss上投了Java后端开发都没有回音,boss上有面试机会都是C#工控软件开发方向的,但是这个方向不太懂,资料又少,面试的表现有点差,现在还是想看看Java这边,面试的时候比较有把握点。想请教一下,这份简历还有什么问题,一直没什么机会,还有什么地方要修改的。
程序员小白条:学历太差,民办和公办,外包还得区分的,这个学历+这个简历,没的办法,除非你有人脉,太难了,这环境,何况你都毕业了,连一段实习都没,肯定没公司会挑选了,没竞争力,开发才招几个人,跟你竞争的可不是二本,三本的人哦,何况你在二本,三本里面也排名不高
投递小天才等公司8个岗位
点赞 评论 收藏
分享
自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务