前置知识

按位与 &

两个数在二进制下按位比较，只有两个数完全相同的时候才会返回1，常用于取某一位

按位或 |

两个数只要有一位是1返回1，常用于合并集合

按位异或 ^

不同为1，相同为0，常用于去重，找不同

按位取反 ~

用的比较少，将所有位取反（符号位也会所以要小心补码）

左移/右移 <</>>

将一个数的二进制位向左或者向右移，相当于*或÷2

状压dp

将状态用二进制压缩起来，一般作为选和不选问题的上位替代
如对于选与不选，可以将选和不选用1/0来代替，再根据这条来转化成二进制，另外创建一个维度来存储二进制长度，如10可以转化成1010表示为选1，3不选2，4，这样，原本要用数组存一大堆「哪些被选过」的信息，现在只用一个整数就能表示，节省空间，方便转移。

P1171

板子题直接套

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn = 21;
int dp[(1<<21)-1][maxn],dis[maxn][maxn];
int n;
int main() {		
		cin>>n;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				cin>>dis[i][j];
			}
		}
		memset(dp,0x3f,sizeof(dp));
		dp[1][0]=0;
		for(int status=2;status<(1<<n);status++) {
			for(int i=0;i<n;i++) {
				if((status>>i)&1) {
					for(int j=0;j<n;j++) {
						int tmp=status^(1<<i);
						if(i!=j&&(tmp>>j)) {
							dp[status][i]=min(dp[status][i],dp[tmp][j]+dis[j][i]);
						}
					}
				}
			}
		}
		int ans=INT_MAX;
		for(int i=0;i<n;i++) {
			ans=min(ans,dp[(1<<n)-1][i]+dis[i][0]);
		}
		cout<<ans;
		return 0;
}

P1879

首先读题得出来三个条件
贫瘠的土地不能种草
一头奶牛一块草地
两块草地不能连在一起
根据这些条件，我们可以先把草地是否贫瘠转成10状态然后再使用状压dp压缩状态，最后枚举每一行进行判断看是否能放置奶牛就行
注意存储的时候要取反
判断和状态转移方程：

CPP

if(status1&(status1<<1)) {
				continue;
			}
			if((status1&f[i])!=0) {
				continue;
			}
			for(int status2=0; status2<(1<<m); status2++) {
				if(status1&status2) {
					continue;
				}
				dp[status1][i]+=dp[status2][i-1];
				dp[status1][i]%=mod;
			}

CPP

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e8;
const int maxn = 15;
int dp[(1<<15)+1][15];
int f[15];
int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		for(int j=0; j<m; j++) {
			int x;
			cin>>x;
			x^=1;
			f[i]|=(x<<j);
		}
	}
	dp[0][0]=1;
	for(int i=1; i<=n; i++) {
		for(int status1=0; status1<(1<<m); status1++) {
			if(status1&(status1<<1)) {
				continue;
			}
			if((status1&f[i])!=0) {
				continue;
			}
			for(int status2=0; status2<(1<<m); status2++) {
				if(status1&status2) {
					continue;
				}
				dp[status1][i]+=dp[status2][i-1];
				dp[status1][i]%=mod;
			}
		}
	}
	int ans=0;
	for(int status=0; status<(1<<m); status++) {
		ans+=dp[status][n];
		ans%=mod;
	}
	cout<<ans;
	return 0;
}

状态压缩dp

文章操作