定义
一种使用位运算的优化型dp（其实就是用于优化）
这里记一下常用的普通表达式的位运算表示（位运算比普通表达式运算时间少一些）：
| 普通表达式 | 二进制表示 |
|---|---|
| pow(2,n) | 1<<n |
| n/2 | n>>1 |
| n*2 | n<<1 |
作用（解决题型）
解决多阶段决策最优化问题（因为是优化型dp，所以解决题型与线性dp差不多）
模板
#include<bits/stdc++.h>
const int INF=1<<15;
using namespace std;
int dp[INF+10];
int dp1[INF+10];
int n,m;
void print1（int num）{
int k=0;
if(num==0)cout<<0;
for(;(1<<k)<=num;k++){
if(num&(1<<k))cout<<1;
else cout<<0;
}
}
int main(){
cin>>n>>m;
while(~scanf("%d",&n,&m)){
int w[20],c[20];
for(int i=0;i<n;i++){
cin>>c[i]>>w[i];
}
int res=-1;
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++){
if(!(i&&(1<<j))){
int temp=i|(1<<j);
dp[temp]=dp[i]+w[j];
dp1[temp]=dp1[i]+c[j];
}
}
}
for(int i=0;i<(1<<n);i++){
print1(i);
cout<<" "<<dp[i]<<" "<<dp1[i]<<endl;
}
}
return 0;
}
例题
洛谷P1896 [SCOI2005]互不侵犯
思路及解题程序（摘自洛谷大佬）%%%
其实只是因为本蒟蒻学了之后还没做出来，之后也许会有一天能够把这道题做出来并发送awa
希望大家不要diss我，靴靴qwq