状压DP I
前言
状压DP其实就是普通DP加上用二进制进行状态压缩，难点应该在于如何压缩状态与找到状态间的关系（更难的恐怕就是得知道这道题是状压DP了把 QAQ）
紫书的题太难，暂时不上紫书的题
- 状压DP
https://hrbust-acm-team.gitbooks.io/acm-book/content/dynamic_programming/state.html - 状压DP入门题 POJ - 3254
https://www.cnblogs.com/Ronald-MOK1426/p/8456945.html
https://blog.csdn.net/harrypoirot/article/details/23163485
Harry And Dig Machine - HDU - 5067
题意
TSP问题，求从点(0,0)出发到所有非0点后回到(0,0)点的最短距离
思路 —— TSP问题
定义dp状态dp[st][i]表示到达状态st（st代表已经经过的点的集合）且i为最后一个到达的点时所走过的最小路径长度，则dp[st][i] = min{dp[st^i][j] + dist[j][i], j ∈ st^i}，即能走到st状态的dp值加上该点到i的距离，其中取最小值
由于走的是环路，所以需要额外处理一下边界值 dp[{i}][i] = dist[0][i]，即先从0出发到点i，但是0点不计入已访问的点
最后的答案就是 dp[{0,1,2,...,n-1}][0] 即 dp[(1 << n) - 1][0]
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 11 + 1;
const int MOD = (int)1e9;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int dp[1 << N][N];
int x[N], y[N], pp;
int dist[N][N];
inline int mabs(int x){ return x < 0 ? -x : x; }
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
memset(dp, 0x3f, sizeof(dp));
memset(dist, 0, sizeof(dist));
pp = 0;
x[pp] = y[pp] = 0;
pp++;
for(int i = 0; i < n; i++){ //为了计算dist，存下x和y坐标
for(int j = 0; j < m; j++){
int tmp;
scanf("%d", &tmp);
if(tmp){
x[pp] = i, y[pp] = j;
pp++;
}
}
}
for(int i = 0; i < pp; i++){ //计算dist
for(int j = i + 1; j < pp; j++){
dist[i][j] = dist[j][i] = mabs(x[i] - x[j]) + mabs(y[i] - y[j]);
}
}
for(int i = 0; i < pp; i++){
dp[1 << (pp - i - 1)][i] = dist[0][i];
}
for(int st = 1; st < (1 << pp); st++){
for(int i = 0; i < pp; i++){
if((st & (1 << (pp - i - 1))) == 0) continue; //点i不在st中说明是非法状态
int prest = st^(1 << (pp - i - 1)); //可以走到i的状态是将i的对应为置0
for(int j = 0; j < pp; j++){
if((prest & (1 << (pp - j - 1))) == 0) continue;
dp[st][i] = min(dp[st][i], dp[prest][j] + dist[j][i]);
}
}
}
printf("%d\n", dp[(1 << pp) - 1][0]);
}
}
Ingress - HDU - 5711
题意
求从点(0,0)出发回到点(0,0)，经过每个点可以hack若干次，第一次会获得a[i]分，随后每一次得到的分数都会下降b[i]分，直到为0，求在走的总路径不超过l，总hack次数不超过k的情况下，得分最大值
思路 —— TSP问题
和上题类似，不过如果定义状态dp[st][i][k]，代表走到i时到达st状态且这个点hack了k次所能得到的最大分数，看上去是没错的，但是会MLE！
于是仍然与上题一样维护长度最小值，最后再用枚举状态，找出dp[{0,..}][0]dp状态，且该状态下值 < l，再贪心思想，用优先队列优先选k个大的，就可以了
这样做的正确性在于，对于每一个到达0的状态，我们都取了最短路径，因此每一种可能性都顾及到了，而考虑k次hack与如何经过这些状态的点无关，所以直接对每一种可能性贪心即可
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
const int N = 17;
const int MOD = (int)1e9;
typedef long long ll;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> pii;
int dp[1 << N][N];
int a[N], b[N];
int dist[N][N];
priority_queue<pii, vector<pii>, less<pii> > que;
void floyd(int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int k = 0; k < n; k++){
dist[i][j] = dist[j][i] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int getVal(int st, int k, int n){
while(!que.empty()) que.pop();
for(int i = 0; i < n; i++){
if(st & (1 << (n - i - 1))) que.push(make_pair(a[i], i));
}
int ret = 0;
while(k--){
pii cur = que.top();
que.pop();
ret += cur.first;
que.push(make_pair(max(0, cur.first - b[cur.second]), cur.second));
}
return ret;
}
int main(){
int t, csn = 1;
scanf("%d", &t);
while(t--){
int n, m, k, l;
scanf("%d%d%d%d", &n, &m, &k, &l);
memset(dp, 0x3f, sizeof(dp));
memset(dist, 0x3f, sizeof(dist));
for(int i = 0; i <= n; i++) dist[i][i] = 0;
a[0] = b[0] = 0;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
while(m--){
int u, v, c;
scanf("%d%d%d", &u, &v, &c);
dist[u][v] = dist[v][u] = min(dist[v][u], c);
}
floyd(++n);
for(int i = 1; i < n; i++){
if(dist[0][i] > l) continue;
dp[1 << (n - i - 1)][i] = dist[0][i];
}
for(int st = 1; st < (1 << n); st++){
for(int i = 0; i < n; i++){
if((st & (1 << (n - i - 1))) == 0) continue;
int prest = st^(1 << (n - i - 1));
for(int j = 0; j < n; j++){
if((prest & (1 << (n - j - 1))) == 0) continue;
dp[st][i] = min(dp[st][i], dp[prest][j] + dist[j][i]);
}
}
}
int ans = 0;
for(int st = 0; st < (1 << n); st++){
if((st & (1 << (n - 1))) == 0) continue;
if(dp[st][0] > l) continue;
ans = max(ans, getVal(st, k, n));
}
printf("Case %d: %d\n", csn++, ans);
}
}
color II - HDU - 5823
题意
图的染色问题，求对每一个子集染色最少需使用多少种颜色，答案输出 sum(点的集合S染色最少颜色种数*233^(2^u1 + 2^u2 + ...), u ∈ S)
思路 —— 图的染色问题
模板题
按紫书的介绍就是，定义dp状态dp[s]，代表将集合s染色所需最少颜色种数，则dp[s] = dp[s - subs] + 1，其中subs是可以染成同一颜色的s的子集（可以是s）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 18;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int G[N][N];
char s[N];
int dp[1 << N];
bool ok[1 << N];
int main(){
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
for(int i = n - 1; i >= 0; i--){
scanf("%s", s);
for(int j = n - 1; j >= 0; j--){
G[i][j] = s[n - j - 1] - '0';
}
}
ok[0] = true;
for(int st = 1; st < (1 << n); st++){ //预处理判断是否可以染成同一颜色
ok[st] = true;
for(int i = 0; i < n; i++){
if((st & (1 << (n - i - 1))) == 0) continue;
for(int j = i + 1; j < n; j++){
if((st & (1 << (n - j - 1))) == 0) continue;
if(G[i][j]){
ok[st] = false;
break;
}
}
if(!ok[st]) break;
}
}
dp[0] = 0;
for(int st = 1; st < (1 << n); st++){
dp[st] = inf;
for(int subst = st; subst; subst = st & (subst - 1)){ //高效枚举st的子集
if(ok[subst]) dp[st] = min(dp[st], dp[st - subst] + 1);
}
}
unsigned fac = 233, ans = 0;
for(int st = 1; st < (1 << n); st++){
ans = ans + fac*dp[st];
fac = fac * 233;
}
printf("%u\n", ans);
}
}
Corn Fields - POJ - 3254
题意
给定01矩阵，其中1上面可以种草，0的不行，现在规定相邻土地上不能种草，问有多少种种法（可以全部不种）
思路
首先枚举每一行可行的状态（根据01矩阵）
然后定义dp状态dp[st][i]，表示种到第i行时前i行的种植方案数量，则dp[st][i] = sum(dp[prest][i - 1])，其中prest要和st满足上下不相邻
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 400 + 15;
const int MOD = (int)1e9;
typedef long long ll;
int cur[N];
int state[N], pst;
ll dp[N][N];
void initState(){
pst = 0;
for(int i = 0; i < (1 << 12); i++){
if(!(i&(i << 1))) state[pst++] = i;
}
}
int main(){
initState();
int n, m;
while(~scanf("%d%d", &n, &m)){
for(int i = 0; i < n; i++){
cur[i] = 0;
for(int j = 0; j < m; j++){
int tmp;
scanf("%d", &tmp);
if(tmp) cur[i] += (1 << (m - j - 1));
}
}
for(int j = 0; j < pst; j++){
if(state[j]&(~cur[0])) dp[0][j] = 0;
else dp[0][j] = 1;
}
for(int i = 1; i < n; i++){
for(int j = 0; j < pst; j++){
dp[i][j] = 0;
if(state[j]&(~cur[i])) continue;
for(int k = 0; k < pst; k++){
if(state[j]&state[k]) continue;
dp[i][j] = (dp[i][j] + dp[i - 1][k])%MOD;
}
}
}
ll ans = 0;
for(int j = 0; j < pst; j++){
ans = (ans + dp[n - 1][j])%MOD;
}
printf("%lld\n", ans);
}
}
【P1896】[SCOI2005]互不侵犯 - 洛谷
思路
与上一题类似，但是要多加一个维度记录下前i行共摆了多少个King，以及判断与上一行的关系的时候除了要判断上下相邻，还要判断两条对角线相邻
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 9 + 1;
const int MOD = (int)1e9;
typedef long long ll;
ll dp[N][1 << N][N*N];
int state[N*N], pst;
int getCnt(int x){
int ret = 0;
while(x){
x = (x & (x - 1));
ret++;
}
return ret;
}
void init(int n){
pst = 0;
for(int i = 0; i < (1 << n); i++){
if(i & (i << 1)) continue;
if(i & (i >> 1)) continue;
state[pst++] = i;
}
}
int main(){
int n, k;
while(~scanf("%d%d", &n, &k)){
init(n);
memset(dp, 0, sizeof(dp));
for(int i = 0; i < pst; i++){
int st = state[i];
int cnt = getCnt(st);
if(cnt > k) continue;
dp[0][st][cnt] = 1;
}
for(int i = 1; i < n; i++){
for(int p = 0; p < pst; p++){
int st = state[p];
int cnt_st = getCnt(st);
for(int j = cnt_st; j <= k; j++){
for(int q = 0; q < pst; q++){
int prest = state[q];
if(st & prest) continue;
if(st & (prest << 1)) continue;
if(st & (prest >> 1)) continue;
dp[i][st][j] += dp[i - 1][prest][j - cnt_st];
}
}
}
}
ll ans = 0;
for(int i = 0; i < pst; i++){
int st = state[i];
ans += dp[n - 1][st][k];
}
printf("%lld\n", ans);
}
}
