题目描述
德玛西亚是一个实力雄厚、奉公守法的国家，有着功勋卓著的光荣军史。这里非常重视正义、荣耀、职责的意识形态，这里的人民为此感到强烈自豪。有一天他们想去制裁邪恶的比尔吉沃特，于是派遣了自己最优秀的战士。结果比尔吉沃特领土太小，只有长为n宽为m共计n*m块土地，其中有些土地标记为0表示为高山峻岭或者深海湖泊，英雄们无法在其中站立，只有标记为1的土地才能容纳一个英雄。德玛西亚的英雄们战斗时有一个特点，他们不希望队友站在自己旁边显得很暧昧。请问最多能有多少种安排德玛西亚英雄的方法？
输入描述
输入包含多组测试数据；
整数n和m (n <= 12, m <= 12 )，之间用空格隔开；
每组数据的第一行包含2个接下来的n行，每行m个数，表示n*m的比尔吉沃特领土。
输出描述
输出一个整数n代表安排应用的方法。（答案取膜100000000）
示例输入
3 3
1 1 1
0 1 1
1 0 0
示例输出
24
题解
状态压缩：例如某行状态为0 0 1 1，那么可以压缩为二进制数字0011，也就是十进制数字3；
用1表示站立英雄，0表示空地。首先枚举英雄在一行中站立的所有可能状态（行中不相邻状态），即i&(i<<1)==0的状态。（若相邻，则左移一位后会和旁边的1对上，相与后就不为0了），枚举后存到数组里。
随后读入地图。同样将每一行状态压缩，存在一维数组里。值得注意的是，为了方便以后判断该行是否适用某一种英雄放置状态，我们可以将空地设为0，不可站立地设为1。这样，当地图状态与英雄放置状态相与时，如若英雄站立在不可站立地时，同位两个1相与会使结果不为零，就能很简单的排除。
然后是转移方程。dp[i][j]表示第i行状态为j时的放置方式总数。dp[i][j]怎么计算呢？显然，首先要看j状态能否和第i行的地图匹配。如果j状态下有英雄站在不可站立地上，那么显然这种状态不可行，dp[i][j]为0；然后，如果i为首行，那么dp[i][j]=1，如果i不为1，那么枚举第i-1行的所有状态k，一旦两行状态不冲突（列中不相邻状态），即k&j==0，那么dp[i][j]+=dp[i-1][k];
所求结果就是dp最后一行所有状态之和啦。当然别忘了时时取膜。
粉丝的输入法大有问题……
#include<stdio.h>#include<string.h>#define ll long long#define MOD 100000000ll map[12],rec[378];int dp[12][378];int n,m;int main(){int temp=0;ll maxm=1<<12;for(ll i=0;i<maxm;i++)if(!(i&(i<<1))) rec[temp++]=i;rec[temp]=maxm;/*枚举13位以内所有可能的放置状态*/while(~scanf("%d%d",&n,&m)){memset(dp,0,sizeof(dp));memset(map,0,sizeof(map));maxm=1<<m;/*规定放置状态的最大位数（避免在三位的地图里放置1111等）*/for(int i=0;i<n;i++)for(int j=0;j<m;j++){scanf("%d",&temp);if(!temp) map[i]+=1<<j;/*压缩地图*/}for(int j=0;rec[j]<maxm;j++)if(!(rec[j]&map[0])) dp[0][j]=1;for(int i=1;i<n;i++)for(int j=0;rec[j]<maxm;j++){if(!(rec[j]&map[i])){for(int k=0;rec[k]<maxm;k++)if(!(rec[j]&rec[k])) dp[i][j]+=dp[i-1][k],dp[i][j]%=MOD;}}temp=0;for(int j=0;rec[j]<maxm;j++) temp+=dp[n-1][j],temp%=MOD;printf("%d\n",temp);}return 0;}
如果觉得《全国多校算法寒假训练营练习比赛（第二场） F.德玛西亚万岁（状压动归）》对你有帮助，请点赞、收藏，并留下你的观点哦！
