链接：/acm/contest/74/F
来源：牛客网
题目描述
德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。 这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。 有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。 结果比尔吉沃特领土太小，只有长为n宽为m共计n*m块土地，其中有些土 地标记为0表示为高山峻岭或者深海湖泊，英雄们无法在其中站立，只有标 记为1的土地才能容纳一个英雄。德玛西亚的英雄们战斗时有一个特点，他 们不希望队友站在自己旁边显得很暧昧。请问最多能有多少种安排德玛西 亚英雄的方法？输入描述:
输入包含多组测试数据；
每组数据的第一行包含2个整数n和m (n <= 12, m <= 12 )，之间用空格隔开；
接下来的n行，每行m个数，表示n*m的比尔吉沃特领土。
输出描述:
输出一个整数n代表安排应用的方法。
（答案取膜100000000）
示例1
输入
3 31 1 10 1 11 0 0
输出
24
题解
状压$dp$。
$dp[i][j][k]$表示到第$i$层，放置了$j$个人，且第$i$层的放置状态为$k$的方案数。
有很多优化可以做，没做优化也可以过。
#include <bits/stdc++.h>using namespace std;int n, m;int a[20][20];int h[20];long long dp[15][80][4100];long long mod = 100000000LL;int cnt[4100], error[4100];int limit = 75;int lowbit(int x) {return x & (-x);}void init() {for(int i = 1; i < (1 << 12); i ++) {cnt[i] = cnt[i - lowbit(i)] + 1;}for(int i = 0; i < (1 << 12); i ++) {for(int j = 0; j < 12; j ++) {int A = i & (1 << j);int B = i & (1 << (j + 1));if(A && B) error[i] = 1;}}}int main() {init();while(~scanf("%d%d", &n, &m)) {for(int i = 1; i <= n; i ++) {h[i] = 0;for(int j = 0; j < m; j ++) {scanf("%d", &a[i][j]);h[i] = h[i] * 2 + a[i][j];}}dp[0][0][0] = 1;for(int i = 1; i <= n; i ++) {for(int num = 0; num <= limit; num ++) {for(int now = 0; now < (1 << m); now ++) {dp[i][num][now] = 0;if(error[now]) continue;if((now | h[i]) != h[i]) continue;if(num - cnt[now] < 0) continue;for(int pre = 0; pre < (1 << m); pre ++) {if(pre & now) continue;dp[i][num][now] = (dp[i][num][now]+ dp[i - 1][num - cnt[now]][pre]) % mod;}}}}long long ans = 0;for(int num = 0; num <= limit; num ++) {for(int now = 0; now < (1 << m); now ++) {ans = (ans + dp[n][num][now]) % mod;}}printf("%lld\n", ans);}return 0;}
如果觉得《全国多校算法寒假训练营练习比赛（第二场）F - 德玛西亚万岁》对你有帮助，请点赞、收藏，并留下你的观点哦！
