演算法分析
棋盤型狀態壓縮dp
這類dp有一個通用的狀態表示法：f[i][j][k],表示前i行（放了j個棋子后）的狀態表示為k，
由于本題無棋子要求，因此可以省去中間一維，
即:
??用f[i][j]表示前i行土地的狀態為j，
首先由于玉米地有不肥沃的地方不能種植，因此需要通過二進制表示出來可以種植和不可以種植的地方，
我們是將整行用一個二進制數表示的，可種為0，不可種為1，在輸入的時候即可判斷：
??g[i] += (!x<<(j-1)) //g[i]為每一行土地的二進制表示
由于是棋盤型，因此根據我們的經驗顯而易見可以知道需要分別分析棋盤的列和行：
根據題意相鄰的兩格內不能同時種玉米可知：
??（以x為當前格）則 ?(x&x>>1)=0;
?? 這很容易理解，比如x的二進制表示為1101，則x>>1 = 0110,可以得出x&x>>1的結果和題目要求相同；
再分析每一列，由于上下列不能同時種玉米：
??(y為相同列不同行的玉米地）因此(y&y-1)=0;
T.T好累
先看代碼吧：
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=13,mod = 1e8;
int f[N][1<<N];
int g[N];
vector<int> state;
vector<int> le_state[1<<N];
bool check(int x)
{
return !(x&x>>1);
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
int x;
scanf("%d",&x);
g[i]+=(!x<<(j-1));
cout<<g[i]<<endl;
}
}
for(int i=0;i<(1<<m);i++) {
if(check(i)) {
state.push_back(i);
}
}
for(int i=0;i<state.size();i++) {
for(int j=0;j<state.size();j++) {
if(!(state[i]&state[j])) {
le_state[i].push_back(j);
}
}
}
f[0][0]=1;
for(int i=1;i<=n+1;i++) {
for(int j=0;j<state.size();j++) {
if(state[j]&g[i]) continue;
for(int b=0;b<le_state[j].size();b++) {
f[i][j] = (f[i][j] + f[i-1][le_state[j][b]])%mod;
}
}
}
cout<<f[n+1][0];
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/543863.html
標籤：其他
上一篇：什么是Python裝飾器？