qbxt dp 笔记

· · 个人记录

DP

最优化原理

状态表示

  1. 具有最优化子结构
  2. 具有简洁性
  3. 能够同时全面的描述一个局面

优化

  1. 减少状态维数
  2. 加速状态转移——数据结构优化或性质分析

记忆化搜索

记忆化搜索的效率可能相对普通 dp 效率更高，其搜到的结果必然是有用的

拓扑图 dp

序列dp

单调队列优化

对于两个决策 j_1 < j_2

若 dp[j_1] < dp[j_2] ，则当 i-j_1 > k , i-j_2 <=k 时，则 j_2 能代替 j_1 ，都有可能称为最小值

若 dp[j_1]\geq dp[j_2] ，则无论何时， j_1 都不可能比 j_2 优，直接删除

每次再队列末尾插入删除一个数或者再队首弹出一个数，保证队列单调递增

括号序列模型

Catalan数

  2. 有 n 对括号形成的合法的括号序列有多少

  4. 凸多边形的三角形划分数

    方程

    f[n] = \sum_{i=0}^{n-1}{f[i] * f[n-1-i]}

    通项： \frac{C(2n,n)}{n+1}

区间dp

区间 dp 一般就是设 dp[i][j] 表示区间 [i,j] 所能形成的最优答案或方案数

环形问题

背包 dp

对于背包问题的实际应用，要寻找什么是容量，什么是物品，什么是物品的费用，什么是物品的价值

一类套路题

给你 N 颗宝石，每颗宝石都有重量和价值 V 要你从这些宝石中选取一些宝石, 保证总重量不超过 W, 且总价值最大为, 并输出最大的总价值, 每颗宝石的重量符合 a*2^b

V \leq 10^9, a \leq 10, b \leq 30

按照 2^b 分组

将物品按照 b 值从大到小排序，分阶段处理，在阶段内 b 值都相同，直接忽略不足 2^b 的部分， f[i][j] 表示前 i 层物品，剩余的能用的重量为 j* 2 ^b 的最大价值

从上一阶段向下一阶段转移时，将 f[i][j] -> f[i][j*2 + ...] ，注意到 n=100 , a \leq 10 ，所以剩余重量最多纪录到 1000 即可

复杂度： O(n*1000)

整数划分问题

  1. 把 n 划分为 k 个正整数的方案数

    法一：暴力 dp

    法二：设 dp[i][j] 表示把 i 划分为 j 个数的方案数

    则可以得到： dp[i][j] = dp[i-j][j] + dp[i-1][j-1]

  2. 法一：暴力，本质是 0/1 背包 法二：$dp[i][j] = dp[i-j][j] + dp[i-j][j-1]

  3. 把 n 划分为 k 个不大于 m 的互不相同正整数的方案数

    dp[i][j]=dp[i-1][j]+dp[i-j][j-1]-dp[i-(m+1)][j-1]

例：给定一个杠杆，等距均匀分布一共 2n+1 个等重质点，支点在 n+1 处，求拿走 k 个质点后使杠杆仍然保持平衡的方案数 \bmod p 的方案数

本题即为从 -n ~ n 中求选出 k 个不同的数，和为 0 的方案数

显然求出来 f[i][j] 表示选出 j 个数和为 i 的方案数，然后枚举其中一端拿走几个 a ，以及拿出的数的重量之和 x ，把 f[x][a] * f[x][k-a] 累加即为方案数

状态转移注意

  1. 分类讨论不重不漏
  2. 讨论时要保证划归到的 dp 状态已经求出来，而不是还未求的
  3. 分类尽量少，使转移更加迅速

数位 dp

一般形式

求区间 [n,m] 满足限制 f(1),...,f(k) 的数字的数量是多少，条件 f(i) 一般与数的大小无关，而与数的组成有关

用不同的进制来处理，一般问题为 10 进制和二进制的数位 dp

例题1

求满足存在连续位为 '13' ， 且模 13 为 0 的数的个数

考虑位为 3 的情况

首先考虑一种特殊情况：n=100...0 ，也就是只要第一位不填 1 后面每一位怎么填都可以

设 N=x_1 x_2 x_3 ... x_t ，我们考虑从高位到地位不断填数 y_1,y_2...

假设到了第 k 位，y_k \neq x_k ，则 k 位之后就没有上限的限制了，情况就简化了

如果前面没有出现 3 ，那么假如我们可以求出 f[k][0] 表示 k 位之后没有上限限制，但是必须填一个 3 ，有多少种填数的方案

如果前面出现了 3 ，那么假如我们可以求出 f[k][1] 表示 k 位之后没有上限限制，但是没有必须出现 3 的限制，有多少种填数的方案

首先我们可以枚举哪一位，然后再枚举这一位是多少，对应的 F 加起来就是答案了，一共需要加 *位数 10** 次

f[k][0]=\sum_{i=0}^{9}{f[k+1][0+[i==3]]} f[k][1]=\sum_{i=0}^{9}{f[k+1][1]}

总复杂度 O(log_{10}(n) * 10^2)

一般使用记忆化搜索来实现

例题2

设 sum(i) 表示 i 的二进制中 1 的个数，给定一个正整数 N ，花神要问你 \displaystyle \prod_{i=0}^{N}{Sum(i)} ，也就是 sum(1)-sum(N) 的乘积

枚举 1 的个数 k ，计算有多少个数含有 k 个 1 ，转化未数位 dp 的模型了另外，发现含有 k 个 1 可能非常多，快速幂处理即可

小技巧

  1. 注意 n=0,m=0 特殊处理
  2. 正难则反
  3. dp初始化 memeset 要置为 -1
  4. 记忆化搜索可以剪枝
  5. 注意特殊处理前导 0

树形 dp

例一

求树的最大独立集（最大独立集指一个最大的点集使得其中的点两两没有边相连）

设 dp[i][0/1] 表示做完了 i 的子树， i 点是否选的最大独立集

dp[i][0]=\sum_{j\in sons}{max(dp[j][0],dp[j][1])} dp[i][1]=\sum_{j\in sons}{dp[j][0]}

例二

求树的直径

一条路径可看为路径中一边与该边两端点到对应直径端点的距离和，在DP中处理最大值，并维护最长链即可

for(int i=head[x];i;i=s[i].nxt)
{
    ll y=s[i].v;
    ll w=s[i].w;

    if(vis[y]) continue;

    dp(y);

    ans=std::max(ans,d[x]+d[y]+w);
    d[x]=std::max(d[x],d[y]+w);
}

例三

给定一棵有 n 个点的树，以及 m 条树链，其中第 i 条树链的价值为 w_i ，求没有公共点的树链的价值和的最大值

设 f[x] 表示为以 x 为根的子树内选取不相交树链的价值和的最大值，枚举一条 LCA 为 x 的链，那么当前方案的价值为 w 加除去该路径上的点后深度最小的点的 f 的和

复杂度： O(M*N)

例四

给出一棵二叉树，点数为 n ，要求每个点和其左儿子和其右儿子三者两两之间颜色互不相同，求最多能有多少点被染成绿色

设 f[i][0] , f[i][1] , f[i][2] 分别表示根是红绿蓝三种颜色时的最多或者最少的数量

例五

给出一棵树，每个点上都有 W_i 的矿石，现在可以在一些点上设立仓库，每设立一个仓库，就要花费 K 的代价，最后每个点的代价如下计算，如果离他最近的点的距离为 dis ，则代价为 W_i \times f(dis) ，最小化总代价。树边长度都为 1

考虑 f[i][j] 表示 i 的子树内所有点都确定了往哪送，并且 i 送到 j ，且 j 点现在还未建立仓库（准确来说是 j 号点 k 的代价还没计入 dp 值内） 的最小代价

转移，首先要加上从 i 到 j 的代价，然后考虑 i 的每一个儿子 i` ，如果 i` 也运到 j ，那么这个子树的代价就是 f[i`][j] ，如果 i` 运到一个不等于 j 的点 j` ，那么 j` 一定在以 i` 为根的子树里，这样每一个被建立的仓库只会被算一次

最终答案为 min(f[1][i]) + k

复杂度 O(n^3)

树上背包

给出一棵 n 个点的有根树，每个节点都是一个物品，具有价值 v_i ，如果一个物品要被选择，那么他的父亲必须被选择，求至多选 m 个物品的最大价值和

$$ f[i][j]=max\{ f[i][j-k] + f[son][k] | k=0 ... (j-1) \} $$ 考虑我们每次合并时相当于是一组点对数量的复杂度，总的来看的话就是 $n$ 个点点对的数量，均摊复杂度 $O(n^2)

DFS 序上 dp

在 DFS 序上 dp ，如果不选一个点，则跳过代表他的子树的 dfs 上连续一段

设 f[i][j] 表示 dfs 序上第 i 个点到第 n 个点，选了 j 的重量得到的最大的价值是多少， i 若不选则跳过整个子树

设 T[i] 表示 dfs 序为 i 的点标号

不选： f[i+siz[T[i]]][j]

选： f[i+1][j-w[T[i]]]

两种情况取最大值即可 （O(n^2)）

another

我们不是每次将孩子与自己合并，而是直接把 dp 数组复制再传给孩子，再从孩子递归下去，最后原来自己的 dp 数组和孩子的 dp 数组直接再对应重量的价值中取 max

换根树形 dp

一棵边带权值 n 个点的树，求每个点在树上的最远距离

我们需要处理子树的信息，同时我们还需要知道父亲那一枝的信息

进行两边 dfs

  1. 一遍求出每个点子树内的信息
  2. 另一遍从根往下遍历的时候计算维护出每个点父亲枝的信息

设 dp[u][0] 是向下最长的， dp[u][1] 是向下次长的， dp[u][2] 是向上最长的

在前面的题目当中，以 1 号点为根 dfs1 之后，我们就得到一号点（根）所需的所有信息。如果我们要求全局的答案，我们可以枚举每个根都这个算一遍，但复杂度就太高了

我们发现如果我们知道了 1 号点作为根的所有信息，通过一些加加减减我们就可以得到 1 号点的孩子作为根所用的信息，我们现在就视一号点的孩子为根了，这就完成了一个换根操作。这个过程还是要用 dfs 来实现。

基环树

即为在树上加一条边（ n 个点 n 条边不一定是个基环树，准确来讲是基环树森林）

例一

本题即求基环内向树森林的带权最大独立集 这里基环树上有且仅有一个环，就是从任意环上一条边断开环，分为两种情况：对于边 $(u,v)$ ，选择 $u$ ，或者选择 $v$ ，两种情况取最大值。转化成树，就是一个树形 dp #### 例二 求基环森林中的每棵基环树的直径之和 1. 在以一个环上节点为根的外向树的直径 做树形 dp 即可 2. 以两个环节点分别为根的最大深度再加上两个节点在环上距离 处理出以环上每个节点为根的最大深度 $d[i]$ ，环上的点重标号，选环上 1 号点作为基准点，求出 $s[i]$ 表示 $i$ 号点到 $1$ 号点的距离， $sum$ 为环的总长，设我们找的两个环上节点为 $i,j

则

max(min{s[i]-s[j],sum-(s[i]-s[j])} + d[i]+d[j])

即为所求

考虑将 min 去掉，分情况讨论

当 s[j] \geq s[i] - sum/2 ，求 d[j]-s[j] 的最大值即可，注意可选的 j 区间会移动，所以需要单调队列维护

反之，这个可行区间只会变大，不会缩小，所以直接记录 s[j]+d[j] 的最大值即可

dp 常见优化

前缀和优化

求长度为 n ，逆序对为 k 的排列有多少个

设 dp[i][j] 表示插入前 i 位，产生的逆序对为 j 的排列的方案数，转移时就考虑 i+1 的那个数插在哪里即可

如果其插在最后，则 dp[i+1][j+0]+=dp[i][j] ，倒数第二位为： dp[i+1][j+1]+=dp[i][j] ，依此类推

即为从前向后更新

考虑 dp[i][j] 从哪些状态转移过来

我们设： f[i][j] = \sum_{k=0}^{j}{dp[i][k]}

则 dp[i][j]=f[i-1][j]-f[i-1][j-i]

通过记录前缀和，将转移优化为 O(1)

在 dp 的基础上，做容斥原理，利用整数划分求解即可

单调队列优化

设 f[i][j] 表示第 i 天手里持有 j 的股票的最大收益 则：

f[i][j]=f[i-1][j] f[i][j]=f[i-w-1][k] - ap[i]*(j-k)|k \geq j - as[i] f[i][j]=f[i-w-1][k] + bp[i]*(k-j)|k \leq j + bs[i]

对于买入：我们可以变形：

f[i][j]=f[i-w-1][k]-ap[i]*(j-k)=f[i-w-1][k]+ap[i]*k - ap[i]*j

则只有最后一项与 j 有关

故可以进行单调队列优化，维护 f[i-w-1][k]+ap[i]*k ，这样 f[i][j] 可以 O(1) 求得，卖出同理

差异

树状数组与线段树优化

求最长上升子序列

状态转移： dp[i]=max{dp[j]|a[j]<a[i] \&\& j<i}+1

将 a[j] 看成坐标， dp[j] 看成权值，每次求坐标小于等于某个值的权值最大值，然后每算完一个单点修改即可

总结

一般先设出 dp 式子，然后观察满足优化模型，就可以进行优化

分析状态

状态压缩 dp

例一

给出 n*m 的棋盘，放上棋子，要求不能有任意两个棋子相邻

设 dp[i][j] 记录第 i 行的摆放情况

转移：

dp[i][s]=\sum{dp[i][s`] | s \& s` == 0}

状压 dp 本质是暴力记录状态，其中有一维是指数级的

例二

设 $dp[i][j][S]$ 表示 $i$ 行用了 $j$ 个国王，当前的状态为 $S

则：

dp[i][j][S]=\sum{dp[i][j-cnt[S]][S`]} judge: (S<<1 | S>>1 | S) \& S` == 0

复杂度： O(n*Fibonacci^2) < O(n* 2^n)

位运算

对于第六条，复杂度为：O(n^3)

拓扑序个数问题

给定一张拓扑图，求这张拓扑图有多少中不同的拓扑序

dp[s]$ 表示当前 $s$ 集合心中的点都满足已经在拓扑序中的方案数，转移考虑枚举下一个点选什么，下一个选的点要满足它在 $s$ 中的点选完后的入度为 $0$ ，也就是指向它的点都已经加入拓扑序，转移到 $dp[s|(1<<(i-1))]

例三：愤怒的小鸟

设 f[S] 为已经消灭的猪的集合为 S 时的最少次数，暴力的转移方法为一次枚举抛物线去更新所有 f ，复杂度 O(n^2 * 2^n)

优化：从小到大枚举 S ，每次打掉编号最小的还没消灭的猪，由于包含该猪的抛物线只有 O(n) 种，复杂度： O(n * 2^n)

例四

一共 n 头麋鹿，每头麋鹿有两支角，可以交换两只麋鹿的一些角，计算最小的交换次数，使得任意一头麋鹿的两角的重量之差不超过 c

n\leq 16 , c\leq 10^6

首先，将鹿角进行排序，判断合法与否

操作上限为 n-1 次

首先，将鹿进行分组，通过组的大小减一，来满足题目要求的条件，注意对于一个组，我们将所有角排序，检查是否合法

选尽量多的合法组并起来等于全集，枚举子集的状态压缩 dp 即可

dp[i] = max{dp[j]+dp[i^j] | j \subset i , j == true}

总结

例五

现在有一个具有 n 个顶点和 m 条边的无向图(每条边都有一个距离权值)小明可以从任意的顶点出发，他想走过所有的顶点而且要求走的总距离最小，并且他要求过程中走过任何一个点的次数不超过 2 次

设 dp[S][i] 表示到过点的情况集合为 S ， S 是三进制数

按照旅行商问题求解即可

例六

给出一个 1 ~ n 排列的其中一种最长上升子序列，求原序列可能的种数

令 f[i][j] 表示所选的数字集合为 i ，此时的做最长上升子序列题时那个辅助数组状态为 j ，对于那个数组 h ， h[i] 表示长度为i的上升子序列结尾的最小值。肯定只有数字集合 i 中的一些数出现在了 h 数组中，而j就是出现在 h 数组中的数的集合。而我们每在这个序列末尾加一个数 x ，就会在 h 中把大于 x 最小的数替换掉。而状态中，就是把比 x 高位最近的 1 去掉，然后把 x 这位附为 1 即可(位运算是可以搞的)

时间复杂度

斜率优化

输出 N 个数字，每输出连续一串，它的费用是这串数字和的平方加上一个常数 M ，求最小的费用

设 dp[i] 表示输出到 i 的时候最少的花费， S[i] 表示从 a[1] 到 a[i-1] 的前缀和

则： dp[i]=min{dp[j]+(s[i+1]-s[j])^2 + M}(j<i)

复杂度： O(n^2)

假设在求解 dp[i] 时，存在 j,k(j>k) ，使得从 j 转移比从 k 转移更优

则满足：

dp[j]+(S[i+1]-S[j])^2 + M < dp[k] + (S[i+1]-S[k])^2 + M

展开并移项合并

(dp[j]+S[j]^2)-(dp[k]+S[k]^2) < 2S[i+1](S[j]-S[k])

将 S[j]-S[k] 除去，并将 dp[x]+S[x]^2 记为 f[x] ，有：

\frac{f[j]-f[k]}{S[j]-S[k]} < 2S[i+1]

故当 j>k 时，有上式成立，则 j 转移优于 k 转移

把 (s[i],f[i]) 看为点，那么上式左面可以看为一个斜率形式

当一个数的 dp 值求完了，它的 f 值也已经确定，就可以做出该点

我们考虑：

那么我们可以考虑他们的关系：

$$ \frac{f[j]-f[k]}{s[j]-s[k]} > \frac{f[i]-f[j]}{s[i]-s[j]} > 2s[t+1] $$ $i$ 优于 $j$ ，$k$ 优于 $j$ ，则 $$ \frac{f[j]-f[k]}{s[j]-s[k]} > 2s[t+1] > \frac{f[i]-f[j]}{s[i]-s[j]} $$ $i$ 优于 $j$ ，$j$ 优于 $k$ ，则 $$ 2s[t+1] > \frac{f[j]-f[k]}{s[j]-s[k]} > \frac{f[i]-f[j]}{s[i]-s[j]} $$ 故 $j$ 永远不可能成为决策点，即上图中的上凸点都会被删去，只需维护下凸点 综上，每次加入一个点，用一个数据结构维护下凸包，使得下凸包边斜率增大，上凸包边斜率减小 斜率越大越优 对于下凸包中，只需找到恰好最后一个点斜率使得比所求点斜率小 因为斜率是单增的，那么我们只需要二分找到这个点 由于 $S[i]$ 也满足单调性，故如果一个点如果不是 $i$ 的最优点，那么它必然不是 $i+1$ 的最优点，就意味着我们可以使用单调队列来维护，每次计算新的值时，从单调队列队首弹出那些不可能再合法的元素 ### 期望 dp * 概率 * 期望 * 概率与期望的计算有一个共同的计算技巧:若事件所产生的所有方案都是等概率的，那么一些概率与期望即可转化为一个计数问题，算出后再除以总方案数即可。如求事件符合条件A的概率，则转化为对符合A的方案数的计数问题;若求方案的某种价值的期望值，则转化为所有方案的价值总和的计数问题。 #### 例一 在花园中有 $n$ 棵苹果树以及 $m$ 条双向道路，每条道路的两端连接着两棵不同的苹果树。假设第 $i$ 棵苹果树连接着 $d_i$ 条道路。小Q将会按照以下方式去 采摘苹果: 1. 随机移动到一棵苹果树下，移动到第i棵苹果树下的概率为 $d_i / 2m$ ,但不 在此采摘。 2. 重复以下操作 $k$ 次:等概率随机选择一条与当前苹果树相连的一条道路，移动到另一棵苹果树下，假设当前位于第 $i$ 棵苹果树下，则他会采摘 $a$ 个苹果，多次经过同一棵苹果树下会重复采摘。 请计算小Q期望摘到多少苹果。$n,k\leq 100000,m\leq 200000

本题可以转化为求在每棵苹果树下的概率

显然， $f(0,j)=\frac{d_j}{2m}

那么第一步走每条边的概率都为： \frac{d_j}{2m} * \frac{1}{d_j} = \frac{1}{2m}

故： f(1,j) = \sum_{(u,j)\in e}{\frac{1}{2m}} = \frac{d_j}{2m}

同理： f(i,j) = \frac{d_j}{2m}

于是 ans=\sum_{i=1}^{n}\sum_{j=1}^{k}{f(j,i)*a_i}

例二

你有一个英雄和若干奴隶主，对方每次攻击会从你的英雄和奴隶主中随机选一个造成一点伤害，奴隶主受到攻击后，体力为 0 则死亡，否则若场上奴隶主少于 7 个，则召唤一个 3 点血量的奴隶主，有 T 局游戏，每局给出初始奴隶主的数量 (\leq 7) 和血量 (\leq 3) ，给出 k ，求对方攻击 k 次后你的英雄受到的总伤害值的期望

设 f[i][a][b][c] 表示还有 i 轮攻击，三种血量的奴隶主数量分别为 a,b,c 时，接下来英雄收到的期望伤害

转移只需要枚举当前攻击到的时英雄还是某种奴隶主即可

初始： f[0][a][b][c]=0

每次询问均可 O(1) 回答

例三

NOIP 2016 换教室

首先可以 floyd 求出任意两点间最短路径

可以想到一个显然的dp状态: f[i][j][0/1] 表示前 i 个课程申请了 j 次，且第 i 个是否申请时的最小期望值

转移：

f[i][j][0]=Max\{f[i-1][j][0]+dis(a[i-1],a[i]) , f[i-1][i][1]+k[i-1]*dis(b[i-1],a[i])+(1-k[i-1])* dis(a[i-1],a[i])\} 时间复杂度 $O(v^3+nm)

例四

有 n 轮游戏和 m 种宝物，每种宝物有分数 P_i ，每轮游戏会等概率抛出一种宝物，你可以选择吃或者不吃，第 i 种宝物还有一个限制集合 S_i ，表示只有在 S_i 种的宝物都吃过以后，才能吃第 i 种宝物，求最优策略下的期望得分

n\leq 100 , k\leq 15

设 f[i][S] 为还要进行 i 轮游戏，吃过的宝物集合为 S , 接下来能得到的最大期望得分

f[i][S]=\frac{(\sum_{k\in gift}{MAX(f[i-1][S],f[i-1][S \cup k] + a[k])})}{m}

例五

一个长度为 n 的 01 串按以下方式生成:第 i 个位置有 a_i 的概率为 1 ，(1-ai) 的概率为 0 , 一个01串的价值如下计算:每一个极长全 1 子串的长度的三次方之和例如 101101 的价值为 10 求该 01 串的价值的期望 n<=100000

首先 E(x)^3 与 E(x^3) 不同

如果i之前极长1长度为x，下一个位置再是1， 则这个增量就是 3*x^2+3*x+1

而增量的期望就是 (1-p_i)*0+p_i*E( (x+1)^3-x^3 )=3*E(x^2)+3*E(x)+1

也就是再存一下 E(x^2) 和 E(x) , E(x) 好求，E(x^2) 和上面用一个方法即可

设 E(x)[i] 表示前 i 个位置，结尾的期望长度 E(x)[i]=pi* (1+E(x)[i-1])

设 E(x^2)[i] 表示前 i 个位置，结尾的期望长度平方

E(x^2)[i]=p_i*(E(x^2)[i-1] + E((x+1)^2-x^2)[i-1])=p_i*(E(x^2)[i-1]+ 2*E(x)[i-1]+ 1)

经典问题

  1. 编号为 1 ~ n 的人排成一排，问有多少种排法使得任意相邻两人的编号之差不为 1 或 -1

    排列计数问题考虑把数从小到大插入的过程进行dp

    设 f[i][j] 表示 1∼i 的排列，有 j 组相邻的相差 1 ，且 i 和 i−1 不相邻的方案数

    设 g[i][j] 表示 1∼i 的排列，有 j 组相邻的相差1，且 i 和 i−1 相邻的方案数

    那么考虑插入 i+1 的位置，有：不破坏空位且不与 i 相邻、不破坏空位且与 i 相邻、破坏空位且不与 i 相邻、破坏空位且与 i 相邻（只发生在 g 的转移）4种

    分别推一下方案数即可，最后的答案就是 f[n][0]

    时间复杂度 O(n^2)

  2. 圆桌上摆放着 n 份食物，围成一圈，第 i 份食物所含热量为 c[i] 。相邻两份食物之间坐着一个人，共有 n 个人。每个人有两种选择，吃自己左边或者右边的食物。如果两个人选择了同一份食物，这两个人会平分这份食物，每人获得一半的热量。假如某个人改变自己的选择后（其他 n-1 个人的选择不变），可以使自己获得比原先更多的热量，那么这个人会不满意。请你给每个人指定应该吃哪一份食物，使得所有人都能够满意。

    带环的问题，包括基环树，很多就是断环为链，然后枚举一端的情况，然后退化成序列上的问题

    肯定是要先枚举一下最开始的情况，设 f[i][S] 表示第 i 份食物被两个人吃的状态为 S 是否有可能，这里的 S 表示的是：两个人都没有吃；左边的人吃了右边的没吃；左边的没吃右边的吃了；左右两边都吃了。

    1. 一个人只能吃一边。
    2. 你要使得中间这个人，变了吃的方向，不会吃的热量更多。

    对于这种环形的 dp 问题，很多时候就是先强制第一个必选什么做一遍 dp，再按照另一种情况做一遍 dp，取最优值

    这个问题中我们发现只有相邻的有影响，这才能保证动态规划的无后效性，就是不会影响之前的选择，往往这种情况才能选择用动态规划