前言

直观上看有棋盘类型（入门）和顺序选择（进阶）类型两种状压dp。 棋盘类型包括小国王、炮兵阵地、玉米地等。

棋盘类型

1. 小国王

这里要注意，最好把一列成立的状态存起来，并把每个状态可以转移到第状态存起来。这样转移要快很多很多。

2. 玉米地

3. 炮兵阵地

第一次错误的状态定义：只定义了前边1列的状态，这样转移不出来（仔细想想，不要想当然，从集合角度考虑）正确定义：每次转移的时候用到了前边两列，状态定义前边两列。n和m最大值不同，n<100,m<10,表示压缩列状态第话需要2^100种方案，会超时，应当压缩行状态。

顺序选择类型

4. Kefa and Dishes

题意

n盘菜选m盘吃，n盘菜各有价值。k条规则，每个规则给定菜品a、b和val，表示吃完a立即吃b有val的价值加成。求最大价值。 n <= 18

思路

从0到1<<n枚举菜品状态（有没有被吃掉），按照已经吃掉菜的数量分类，吃了n-1盘菜向n盘菜转移。这时候要考虑那一种状态最后一次吃得是哪一个。 所以dp[i][state]表示上一次吃i且状态为state的最大价值。

坑点

之前定义dp[i][state]为已经吃了i盘菜，状态为state。（state有几个1就确定了吃了几盘菜，i无用），并且用last[state]去记录dp[i][state]最大价值下，上一次吃的菜。事实上下一次更优，有可能是当前价值不是最优得出来的，也就是说不能只记录当前最大价值下上次吃的菜。

思考

比较和别人的代码，发现dp顺序不同，我先把所有状态，按照有几个1分类，再用1个1去更新2个1，2个1更新3个1（见init函数，和dp部分代码），别人则直接从0到(1 << n)的所有状态更新下一个状态。如图所示。 后来想通了，只要对于状态state，state已经被正确更新了，他就可以更新其他状态。我的写法看起来可能更清晰，但是不方便。说一下别人直接从0到（1<<n）更新为什么不会错。 state = 10110(2进制)，则所有能更新10110的状态有00110、10100、10010，也就是去掉任意一个1。所以能更新10110的状态都小于10110，所以枚举到10110时，10110已经被所有能更新他的状态更新过了，所以10110是正确的dp值，所以10110可以更新4个1的状态。

#include<iostream> #include<vector> #include<cstring> #include<cstdio> #define debug(x) cout<<#x<<" = "<<x<<endl #define debug_(x, y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl using namespace std; typedef long long ll; const ll maxn = 20; const ll inf = 0x3f3f3f3f; typedef pair<ll, ll> PII; vector<ll> V[maxn]; ll dp[maxn][1 << maxn]; ll wei[maxn], addition[maxn][maxn]; ll n, m, k, val, a, b; ll count(ll x){ ll cnt = 0; while(x){ cnt += x & 1; x >>= 1; } return cnt; } void init(){ for(ll i=0;i<(1 << n);i++){ ll temp = count(i); V[temp].push_back(i); } } int main(){ cin>>n>>m>>k; init(); for(ll i=1;i<=n;i++) cin>>wei[i]; for(ll i=1;i<=k;i++){ cin>>a>>b>>val; addition[a][b] = val; } // transfer dp[pos][next_state] = max(self, dp[i][state] + wei[pos] + addtion[i][pos]); for(ll i=0;i<m;i++){ for(ll state : V[i]){ for(ll pos = 0; pos < n; pos ++){ if(state >> pos & 1){ continue; }else{ ll next_state = state | (1 << pos); dp[pos][next_state] = wei[pos + 1]; for(ll pos_true = 0; pos_true < n; pos_true ++){ if(state >> pos_true & 1){ dp[pos][next_state] = max(dp[pos][next_state], dp[pos_true][state] + wei[pos + 1] + addition[pos_true + 1][pos + 1]); } } } } } } ll ans = 0; for(ll state : V[m]){ for(ll pos_true = 0; pos_true < n; pos_true ++){ if(state >> pos_true & 1){ ans = max(ans, dp[pos_true][state]); } } } cout<<ans<<endl; return 0; }

5. CHEAP DELIVERIES

#include<bits/stdc++.h> using namespace std; typedef unsigned long long ll; typedef pair<ll, ll> PII; const ll inf = 0x3f3f3f3f; const ll maxn = 1e4 +10; const ll maxk = 20; ll n, m, k; ll h[maxn], w[maxn << 1], e[maxn << 1], ne[maxn << 1], idx; ll dist[maxn]; bool st[maxn]; ll p[maxk][maxk]; ll dp[1 << maxk][maxk]; PII query[maxk]; void addedge(ll a, ll b, ll c){ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; } void dij(ll x){ memset(dist, 0x3f, sizeof dist); memset(st, false, sizeof st); dist[x] = 0; priority_queue<PII, vector<PII>, greater<PII> > heap; heap.push({0, x}); while(heap.size()){ PII t = heap.top(); heap.pop(); ll ver = t.second, distance = t.first; if(st[ver]) continue; st[ver] = true; for(ll i=h[ver]; i!=-1; i=ne[i]){ ll j = e[i]; if(dist[j] > dist[ver] + w[i]){ dist[j] = dist[ver] + w[i]; heap.push({dist[j], j}); } } } } int main(){ memset(h, -1, sizeof h); scanf("%llu%llu%llu", &n ,&m, &k); for(ll i=1;i<=m;i++){ ll a, b, c; scanf("%llu%llu%llu", &a, &b, &c); addedge(a, b, c); addedge(b, a, c); } for(ll i=1;i<=k;i++){ ll a, b; scanf("%llu%llu", &a, &b); query[i].first = a, query[i].second = b; } /// initialize p array memset(p, inf, sizeof p); for(ll i=1;i<=k;i++){ dij(query[i].first); for(ll j=1;j<=k;j++){ p[i][j] = dist[query[j].second]; } } /// initialize dp array for(ll i=0;i<(1 << k);i ++) for(ll j=0;j<k;j++) dp[i][j] = inf; for(ll i=0;i<k;i++){ dp[1 << i][i] = p[i +1][i +1]; } ll ans = inf; /// dp main process for(ll i=0;i<(1 << k);i++){ for(ll start = 0; start < k; start ++){ if((i & (1 << start)) == 0) continue; for(ll to = 0; to < k; to ++){ if(i & (1 << to)) continue; ll next_state = i | (1 << to); dp[next_state][to] = min(dp[next_state][to], dp[i][start] + p[start + 1][to + 1] + p[to + 1][to +1]); if(next_state == (1 << k ) - 1) ans = min(ans, dp[next_state][to]); } } } if(ans != inf) printf("%llu\n", ans); else puts("-1"); return 0; } /* 5 5 3 1 2 1 2 3 2 3 4 3 4 5 4 5 2 4 2 3 1 2 5 3 12 5 5 4 1 2 10 5 3 10 2 4 1 4 1 2 3 5 4 1 2 3 5 4 1 2 4 -1 */