AcWing 327. 玉米田
原题链接
简单
作者:
微笑
,
2019-10-07 15:58:14
,
所有人可见
,
阅读 816
很经典的状压dp,只比国王那个题多了个地图,即只能在1的格子上种玉米,其实也就是当前状态|地图这一行的状态,等于地图的状态,具体的看代码吧
C++ 代码
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 1<<12, mod=1e8;
int dp[13][N],tem[N],top;
int mp[13];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int sum=0,x;
for(int j=0;j<m;j++)
{
cin>>x;if(x) sum+=1<<(m-j-1); //构建地图的状态,注意先遇到的1,在高位
}
mp[i]=sum;
}
for(int i=0;i<(1<<m);i++) //预处理自己与自己不冲突的行的状态
if(!(i&(i<<1))) tem[top++]=i;
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<top;j++)
for(int k=0;k<top;k++)
{
if(!(tem[j]&tem[k]) && (tem[j]|mp[i])==mp[i]) //不与上一行冲突,且不能在地图上0的地方种玉米
dp[i][j]+=dp[i-1][k],dp[i][j]%=mod;
}
}
int ans=0;
for(int i=0;i<top;i++) ans+=dp[n][i],ans%=mod;
cout<<ans<<endl;
return 0;
}