主要原理(常用) 1<<n
用二进制位枚举状态，以达到压缩状态的效果
一个简单的例题
看到\(m\)的范围应该能想到压进1<<10里
唯一的细节:因为这个状态不好排序,所以要分层,最好用滚动
#include<bits/stdc++.h>
using namespace std;
int n,T,m,x,y,f[2][1100];
int main() {
scanf("%d",&T);
for(int kase=1; kase<=T; kase++) {
memset(f,-1,sizeof f),f[0][0]=0;
scanf("%d%d",&n,&m);
for(int i=1,cur=1; i<=n; i++,cur^=1) {
scanf("%d%d",&x,&y);
int k=0;
for(int j=1,t; j<=y; j++)scanf("%d",&t),k|=1<<(t-1);
for(int j=0; j<1<<m; j++) {
f[cur][j]=max(f[cur][j],f[!cur][j]);
if(~f[!cur][j]) {
f[cur][j^k]=max(f[cur][j^k],f[!cur][j]+x);
}
}
}
printf("%d\n",f[n&1][(1<<m)-1]);
}
}
N皇后二进制优化
最优解法 转载自cnblogs
小数据 \(n<=15\) TSP问题 (货郎担问题)
一种版本
\(H<=15\) 可以dp
先 \(floyd\) 跑出\(dis[i][j]\)数组
再状压dp,每种状态用二进制位表示
从每种状态的前状态(i^(1<<j))转移，刷表
转载于:https://www.cnblogs.com/chasedeath/p/11269391.html
