【bzoj 1087】互いにキンク状態を侵さない圧縮dp
ACチャネル:http://www.lydsy.com/JudgeOnline/problem.php?id=1087
【題解】
f[i][j][k]で、前i行がj個の駒を置いた状態で、i行目の状態がkのスキーム数を表す.
vis[i]は状態iが適法かどうかを示し、check[i][j]は状態i,jが隣接していても良いかを示している.
詳細はコードを参照:
【題解】
f[i][j][k]で、前i行がj個の駒を置いた状態で、i行目の状態がkのスキーム数を表す.
vis[i]は状態iが適法かどうかを示し、check[i][j]は状態i,jが隣接していても良いかを示している.
詳細はコードを参照:
/*************
bzoj 1087
by chty
2016.11.15
*************/
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
#define FILE "read"
#define up(i,j,n) for(ll i=j;i<=n;i++)
namespace INIT{
char buf[1<<15],*fs,*ft;
inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline ll read() {
ll x=0,f=1; char ch=getc();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getc();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getc();}
return x*f;
}
}using namespace INIT;
ll n,m,ans,vis[1<<9],sum[1<<9],check[1<<9][1<<9],f[11][121][1<<9];
void pre(){
up(i,0,(1<>=1) sum[i]+=(x&1);}
up(i,0,(1<>1))||(j&(i>>1))) continue;
check[i][j]=1;
}
}
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read(); m=read();
pre(); up(i,0,(1<