Solution
状压 \(dp\) .
\(f[i][j][k]\) 代表前 \(i\) 列中 , 已经安置 \(j\) 块草皮, 且最后一位状态为 \(k\) .
同时多记录一个每一列中的不能放的位置 \(w[i]\).
然后就可以很轻松的转移了...
转移方程看代码.
- Code
- #include<bits/stdc++.h>
- #define ll long long
- using namespace std;
- ll f[13][145][10000],n,K;
- ll JS[10000],m,sum,ans,w[14];
- int main()
- {
- cin>>n>>m;
- sum=(1<<m)-1;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- {
- int x; cin>>x;
- K+=x;
- w[i]=w[i]*2+x^1;
- }
- for(ll i=0;i<=sum;i++)
- for(ll j=0;j<m;j++)
- if(i&(1<<j))JS[i]++;
- for(ll i=0;i<=sum;i++)
- {
- if((i<<1&i))continue;
- if((i&w[1]))continue;
- f[1][JS[i]][i]=1;
- }
- for(ll i=1;i<n;i++)
- for(ll j=0;j<=K;j++)
- for(ll k=0;k<=sum;k++)
- {
- if(!f[i][j][k])continue;
- for(ll kk=0;kk<=sum;kk++)
- {
- if(kk&w[i+1])continue;
- if((k&kk)||(kk<<1&kk))continue;
- if(j+JS[kk]>K)continue;
- f[i+1][j+JS[kk]][kk]+=f[i][j][k];
- }
- }
- for(int j=0;j<=K;j++)
- for(ll i=0;i<=sum;i++)
- ans+=f[n][j][i];
- cout<<ans%100000000<<endl;
- }
来源: http://www.bubuko.com/infodetail-2809417.html