状态压缩？

状态压缩，顾名思义，就是把一个大的状态压成相对来说内存更小的东西（通常来说是一个int数字）。而这样做又有什么好处呢？就是当状态的复制量很大，但修改次数相对较小时占优势。（试想一下如果不用回溯，那么dfs时每一层栈空间都带一个vis数组……）

几种状态压缩

三进制状态压缩

loj#6177. 「美团 CodeM 初赛 Round B」送外卖2

题目描述

一张 n 个点 m 条有向边的图上，有 q 个配送需求，需求的描述形式为 (si,ti,li,ri)，即需要从点 s_i 送到 t_i，在时刻 l_i 之后（包括 l_i）可以在 s_i 领取货物，需要在时刻 r_i 之前（包括 r_i）送达 t_i ，每个任务只需完成一次。

图上的每一条边均有边权，权值代表通过这条边消耗的时间。在时刻 0 有一个工作人员在点 1 上，求他最多能完成多少个配送任务。

在整个过程中，可以认为领货跟交货都是不消耗时间的，时间只花费在路程上。当然在一个点逗留也是允许的。

输入格式

第一行，三个正整数 n,m,q(2≤n≤20,1≤m≤400,1≤q≤10)。
接下来 m 行，每行三个正整数 ui,vi,ci(1≤ui,vi≤n,1≤ci≤20000)，表示有一条从 ui 到 vi 耗时为 ci 的有向边。
接下来 q 行，每行四个正整数 si,ti,li,ri(1≤si,ti≤n,1≤li≤ri≤10^6)，描述一个配送任务。

输出格式

一个整数，表示最多能完成的任务数量。

内存限制：32 MiB时间限制：200 ms标准输入输出

题目分析

我们首先可以发现n和q都是很小的，又注意到这题的时空限制很不寻常，于是可以大胆结合题意猜测一些想法。

其实没什么好猜的我直接步入正题讲状态压缩算了就不讲我那zz的dfs了

对于每一个送货任务来说，一共只有三种情况：0.货还没取；1.取货了没送到；2.已经送到了。

于是考虑状压dfs。

状压怎么压呢？形象一些就是一串长为q的三进制数，例如(021)（q=3），代表第一单货未取；第二单货已送到；第三单货正在配送。

于是用一个int类型的state以十进制的方式存放状态。十进制？那么怎么提取各个状态呢？如同二进制状压一样，我们需要预处理三的各次幂。正是因为状态压缩这样的特性，所以它适用于需要频繁复制状态，而提取状态相对容易的情况。

由于我第一次接触这种三进制状压时候，对于一些从未见过的操作颇有感触，那么就在代码里注释吧。

hint：每一次可以接很多单（在路上跑的时候可以一次拿很多外卖）

代码：

 1 #include<bits/stdc++.h>
 2 const int maxn = 21;　　//n的最大值（一共多少点）
 3 const int max3 = 60003;//送货状态转为十进制数后的最大值，用于最优性剪枝
 4 
 5 struct node
 6 {
 7     int l,r,s,t;
 8     node() {}
 9     node(int a, int b, int c, int d):s(a),t(b),l(c),r(d) {}
10 }a[maxn];　　　　　　　　//存送外卖每一单的需求
11 int ans,n,m,q;
12 int f[maxn][max3],dis[maxn][maxn],base[maxn];　　　　　　//base[]是3的各次幂，用于提取状态
13 
14 int read()
15 {
16     int num = 0;
17     char ch = getchar();
18     for (; !isdigit(ch); ch = getchar());
19     for (; isdigit(ch); ch = getchar())
20         num = (num<<1)+(num<<3)+ch-48;
21     return num;
22 }
23 void dfs(int now, int state, int times)
//now:现在在now这个点上，注意是送货地图的点
//state:现在所有送货的状态
//times:现在已经花费的时间
24 {
25     for (int i=1; i<=q; i++)　　　　　　　　　　　　　　　　//检验在当前这个点，可以取送哪些货物
26     {
27         if (a[i].s==now && (state/base[i-1]%3==0) && times>=a[i].l) state += base[i-1];
　　　　　　 //现在在i单货物起点；i单货物状态为0（没有取货过）；现在能够取这个货物；使这个状态+1（在三进制下变为1）
28         if (a[i].t==now && (state/base[i-1]%3==1) && times<=a[i].r) state += base[i-1];
　　　　　　 //现在在i单货物终点；i单货物状态为1（已经取货了）；现在送这个货物来得及；使这个状态+1（在三进制下变为2）
29     }
30     if (f[now][state] < times) return;　　//最优性剪枝
31     f[now][state] = times;
32     int cpy = state, cnt = 0;
33     while (cpy)
34     {
35         if (cpy%3==2) cnt++;
36         cpy /= 3;
37     }
　　　　//提取当前状态中有多少外卖已经送到了
38     if (ans < cnt) ans = cnt;
39     for (int i=1; i<=q; i++)　　　　　　　　//接下去遍历每一单货物，考虑dfs的后继
40     {
41         if (state/base[i-1]%3==0){
42             int tt = std::max(times+dis[now][a[i].s], a[i].l);
43             if (tt <= a[i].r) dfs(a[i].s, state, tt);　　//如果这一单还没有送，并且现在立即赶过去还来得及，就dfs这一单
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //至于为什么这里不更改i单的状态，是因为不排除dfs这一单后能够同时送到其他单的情况。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //所以我们放在每一次dfs开始的时候更新状态
44         }else if (state/base[i-1]%3==1 && times+dis[now][a[i].t] <= a[i].r)
45             dfs(a[i].t, state, times+dis[now][a[i].t]);  //如果这一单已经在配送过程中了，那么现在去配送这一单
46     }
47 }
48 int main()
49 {
50     scanf("%d%d%d",&n,&m,&q);
51     memset(dis, 0x3f3f3f3f, sizeof dis);　　　 //送货地图上两点之间距离用
52     memset(f, 0x3f3f3f3f, sizeof f);　　　　　　//最优性剪枝用
53     for (int i=1; i<=m; i++)
54     {
55         int x = read(), y = read(), z = read();
56         if (dis[x][y] > z) dis[x][y] = z;
57     }
58     for (int k=1; k<=n; k++)
59     {
60         for (int i=1; i<=n; i++)
61             for (int j=1; j<=n; j++)
62                 if (dis[i][j] > dis[i][k]+dis[k][j])
63                     dis[i][j] = dis[i][k]+dis[k][j];
64         dis[k][k] = 0;
65     }
66     for (int i=1; i<=q; i++)
67     {
68         int ax = read(), b = read(), c = read(), d = read();
69         a[i] = node(ax, b, c, d);
70     }
71     base[0] = 1;　　　　　　　　　　　　　　　　　　//预处理三的幂次（3^0,3^1,3^2……）
72     for (int i=1; i<=q; i++)
73         base[i] = base[i-1]*3;
74     dfs(1, 0, 0);
75     printf("%d
",ans);
76     return 0;
77 }

另，待更，炮兵阵地