状压DP

套路

其实套路挺明显的，也很容易看出来要用状压，所以通常就把一行的状态压缩成一个数（一般适用于放不放棋子这类的只有选/不选两种状态的）
（有可能会有特殊情况，比如炮兵阵地就是三进制状压，这个我们先不管）
核心代码大概长这样，根据不同题的不同限制改一改就行了：

void dp(){
	f[0][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=0;j<sum;j++){//< is rignt,<= is wrong,because 2^n-1 means every figure is 1 in binary system
			if((j>num[i])||((j&num[i])!=j)||(j&(j<<1))||(j&(j>>1))) continue;
			for(int k=0;k<sum;k++){
				if(!(k&j)){
					f[i][j]=(f[i][j]+f[i-1][k])%mod;
				}
			}
		}
	}
}

例题

P1879 Corn Fields G

题目
code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 20
#define ll long long
using namespace std;
template<typename T>
inline void read(T &x){
	x=0;bool flag=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

const int mod=100000000;
int m,n,a[maxn][maxn];
int num[maxn],f[maxn][1<<maxn],sum,ans;

void dp(){
	f[0][0]=1;
	for(int i=1;i<=m;i++){
		for(int j=0;j<sum;j++){//< is rignt,<= is wrong,because 2^n-1 means every figure is 1 in binary system
			if((j>num[i])||((j&num[i])!=j)||(j&(j<<1))||(j&(j>>1))) continue;
			for(int k=0;k<sum;k++){
				if(!(k&j)){
					f[i][j]=(f[i][j]+f[i-1][k])%mod;
				}
			}
		}
	}
}

int main(){
	read(m),read(n);
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			read(a[i][j]);
			num[i]=(num[i]<<1)+a[i][j];
		}
	}
	sum=1<<n;
	dp();
	for(int i=0;i<sum;i++) (ans+=f[m][i])%=mod;
	cout<<ans<<endl;
	return 0;
} 

P1896 互不侵犯

题目
因为限制了k个国王，所以f数组要多开一维记一下国王数量
code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define maxn 15
#define maxm 200
#define ll long long//不开long long要出锅啊 
using namespace std;
template<typename T>
inline void read(T &x){
	x=0;bool flag=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

int n,k;
ll ans,king_yihang,cnt,a[maxm],num[maxm],f[maxn][maxm][maxm];//第i行第j种状态放了k个国王 

void dp(){
	f[0][1][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=cnt;j++){
			for(int t=0;t<=k;t++){
				if(num[j]>t) continue;
				for(int u=1;u<=cnt;u++){
					if((a[u]&a[j])||(a[u]&(a[j]<<1))||(a[u]&(a[j]>>1))) continue;
					f[i][j][t]+=f[i-1][u][t-num[j]];
				}
			}
		}
	} 
}

int main(){
	read(n),read(k);
	for(int i=0;i<=(1<<n)-1;i++){
		king_yihang=0;
		if(i&(i<<1)) continue;
		for(int j=0;j<=n-1;j++) if(i&(1<<j)) king_yihang++;
		a[++cnt]=i;
		num[cnt]=king_yihang;
	}
	dp();
	for(int i=1;i<=cnt;i++) ans+=f[n][i][k];
	cout<<ans<<endl;
	return 0;
}

P4163 排列

题目
code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 1010
#define ll long long
using namespace std;
template<typename T>
inline void read(T &x){
	x=0;bool flag=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') flag=1;
	for(;isdigit(c);c=getchar()) x=x*10+(c^48);
	if(flag) x=-x;
}

int T,d,len,num[20],f[1024][maxn];
char s[20];
bool vis[20];

int main(){
	read(T);
	for(int t=1;t<=T;t++){
		memset(s,0,sizeof(s));
		memset(num,0,sizeof(num));
		memset(f,0,sizeof(f));
		cin>>s+1;read(d);
		len=strlen(s+1);
		for(int i=1;i<=len;i++) num[i]=s[i]-'0';
		f[0][0]=1;
		for(int i=0;i<(1<<len)-1;i++){
			memset(vis,0,sizeof(vis));
			for(int j=1;j<=len;j++){
				if((i&(1<<(j-1)))||vis[num[j]]) continue;
				vis[num[j]]=1;
				for(int k=0;k<d;k++){//********
					f[i|(1<<(j-1))][(10*k+num[j])%d]+=f[i][k];
				}
			}
		}
		cout<<f[(1<<len)-1][0]<<endl;
	}
	return 0;
} 

P2150 寿司晚宴

题目
没写呢，写完再来填坑