poj3254 炮兵阵地弱化版，记数类dp

/* dp[i][j]表示到第i行的状态j有多少放置方式 */ #include<iostream> #include<cstring> #include<cstdio> #include<vector> using namespace std; #define mod 100000000 int dp[15][10000],mp[15][15],cur[15],ans,n,m; vector<int>v; inline int legal(int x){ if(x&(x<<1))return false; return true; } void init(){ v.clear(); ans=0; memset(dp,0,sizeof dp); for(int i=0;i<=(1<<m)-1;i++) if(legal(i)) v.push_back(i); for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(mp[i][j]==0)cur[i]+=(1<<(m-j-1)); } int place(int s,int k){//状态s能否放在第k行 if(s&cur[k])return false; return true; } int main(){ while(cin>>n>>m){ for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>mp[i][j]; init(); for(int i=0;i<v.size();i++)//先处理第0行的情况 if(place(v[i],0))dp[0][i]=1; for(int i=1;i<n;i++) for(int t=0;t<v.size();t++){ if(place(v[t],i)){//如果状态t可以放在第i行 for(int j=0;j<v.size();j++)//枚举i-1行的状态 if(!place(v[j],i-1) || v[t]&v[j])continue; else dp[i][t]=(dp[i][t]+dp[i-1][j])%mod; } } for(int j=0;j<v.size();j++) ans=(ans+dp[n-1][j])%mod; printf("%d\n",ans); } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10358959.html