题目链接：/acm/contest/74/F
题目大意：
给你n*m大小的棋盘，其中1可以放置英雄，0不能放置。而放置英雄的格子的上下左右不能再放置英雄。输出总共有多少种放置方法，结果对100000000取模。
题目分析：
比赛时完全懵逼，只是知道是dp。在赛后看了一位大神的代码才知道如何实现这道题的正确做法。数据n,m最大是12，可以先把这一行12格的摆放方法全部枚举一遍，挑选出可行的状态。再根据选出的可行状态与本行的实际状态是否相匹配，判断这个方法是否可行。
代码如下：
#include <bits/stdc++.h>using namespace std;typedef long long LL;const int mod=100000000;//n为行，m为列。则每行最多有2的m次种状态int n,m,top,state[666]; //state存放可行的放置状态//由于最大为12*12,每行最多有2的12次种状态,其中可行状态则会大大减少int dp[20][666]; //dp存储第i行，符合条件的所有状态int cur[20]; //表示每行可放置的逆，0变1，1变0bool ok(int x) //判断状态是否可行{if(x&(x<<1)) return false;//如果存在相邻的1，则该状态不满足条件return true;}void init() //遍历所有状态{top=0;memset(state,0,sizeof(state));memset(cur,0,sizeof(cur));int x=1<<m; //遍历状态的上限for(int i=0;i<x;i++)if(ok(i)) state[top++]=i;}bool fit(int x,int i) //判断第x行与第i行的逆是否重合{if(x&cur[i]) return false; //若重合，则不能不满足条件return true; //不重合则可行}void sky()//dp函数{memset(dp,0,sizeof(dp));for(int i=0;i<top;i++) //初始化第一行可行状态if(fit(state[i],1)) //判断所有可能状态与第一行实际状态的逆是否重合dp[1][i]=1; //若不重合，则该状态实际可行，第1行第i状态标为1//状态转移方程 dp[i][k]= ∑(dp[i-1][j]) (第i-1行，j为所有符合状态)for(int i=2;i<=n;i++){for(int k=0;k<top;k++) //该循环针对所有可能状态找出符合第i行的状态{if(!fit(state[k],i)) continue;//判断与第i行的实际情况是否符合for(int j=0;j<top;j++){if(!fit(state[j],i-1)) continue; //判断与第i-1行的实际情况是否符合if(state[k]&state[j]) continue; //判断第k种与第j种状态是否冲突dp[i][k]=(dp[i][k]+dp[i-1][j])%mod;//满足以上条件后则进行叠加}}}}int main(){while(scanf("%d%d",&n,&m)!=EOF){init();int num;for(int i=1;i<=n;i++)//输入时就要按位来存储，cur[i]表示的是第i行整行的情况，每次改变该数字的二进制表示的一位for(int j=1;j<=m;j++){scanf("%d",&num); //表示第i行第j列的情况（0或1）if(num==0)cur[i]+=(1<<(m-j));//则将该位置为1（注意要以相反方式存储，即1表示不可放置)}sky();int sum=0;for(int i=0;i<top;i++) //累加最后一行所有可能状态的值，即得最终结果sum=(sum+dp[n][i])%mod;printf("%d\n",sum);}return 0;}
如果觉得《F-德玛西亚万岁(状压DP)（全国多校算法寒假训练营练习比赛（第二场))》对你有帮助，请点赞、收藏，并留下你的观点哦！
