定义
一种使用位运算的优化型dp（其实就是用于优化）
不懂位运算的可以看这儿（其实就是百度传送门）
这里记一下常用的普通表达式的位运算表示（位运算比普通表达式运算时间少一些）：
普通表达式二进制表示
pow(2,n)1<<nn/2n>>1n*2n<<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
<<"\t"<<dp
[i
]<<"\t"<<dp1
[i
]<<endl
;
}
}
return 0;
}
例题
洛谷P1896 [SCOI2005]互不侵犯
思路及解题程序（摘自洛谷大佬）%%%
其实只是因为本蒟蒻学了之后还没做出来，之后也许会有一天能够把这道题做出来并发送awa
希望大家不要diss我，靴靴qwq
更多状态压缩dp合集
