枚举这个“超标”的主食 i。设 f[j][k][l] 表示前 j 种方法中一共选择了 k 个主食 i，一共选择了 l 个主食 的方案数。最终答案为 f[n][u][v]，其中 u > v / 2。这样，我们得到了一种 O(m^2n^3) 的方法。
优化1：
转移的时候把其它菜的方案和预处理一下，可以砍掉转移的一个 m。复杂度： O(mn^3)
优化2：
我们发现最终我们关心的不是 u,v 具体是多少，而是 u, v 的相对大小。因此我们可以再合并一些状态，把状态定义为：f[j][k] 表示前 j 种方法中第 i 种主食比其余主食多 k 个 的方案数。这样可以再状态数上砍掉一个 n。复杂度： O(mn^2)
优化3：
各种卡常。
数据结构优化DP：单调队列优化DP
单调队列优化多重背包详解
题目
仔细观察朴素多重背包的转移方程：
f[j] <- g[j - k * w] + k * v
其中 w 表示当前物品的代价， v 表示当前物品的价值，k 为枚举的数量，需要保证 k <= K
仔细观察发现由于 j - k * w，影响 f[j] 的状态只有与 j 模 w 同余的那些状态，我们把这些状态单独拿出来。这时，问题就有点像“在距离 j 不超过 K 的状态中取最大值”，即“滑动窗口”。故可以使用单调队列优化。这里维护的是一个单调下降的队列。
还差 k * v 没有处理。我们发现 k * v 在提溜出来的那一堆状态里面永远是个公差为 -v 的等差数列，那么我们干脆在加入队列的时候让状态减去 id * v （加入的是提溜出来的数组中的第 id 个），就能保证队列中的相对大小。经过手玩尝试后，知道队列的真实值应该再加上 ct * v（当前是第 ct 个）。
对于每一个剩余系都这样做一下，就能 O(m) 地刷完一遍 f。
//q 记录队列中的值,id 记录队列中状态的位置
for (register int i = 1; i <= n; ++i) {
int w, v, s; read(w), read(v), read(s);
memcpy(g, f, sizeof(g));
for (register int j = 0; j < w; ++j) {
int front = 0, rear = 0;
for (register int k = j, ct = 1; k <= V; k += w, ++ct) {
if (ct - id[front + 1] > s) ++front;
if (front < rear)
MAX(f[k], q[front + 1] + ct * v);
while (front < rear && q[rear] <= g[k] - ct * v) --rear;
q[++rear] = g[k] - ct * v;
id[rear] = ct;
}
}
}
数据结构优化DP：线段树优化DP
数据结构优化DP：平衡树优化DP
T132728 最大价值(value)
按照 a 排序，这样我们加入这个数的时候一定会把它放在最后一位，这样我们就可以用背包来解决了。思路来源：拯救小矮人。
转移方程： f[i][j] <- f[i - 1][j - 1] + (j - 1) * a + b
通过对拍可知，这个转移一定会在 j 挨着 i 的一段状态发生。假设中间点为 k。
由于转移是否尽心与两个相邻的 f 都有关系，我们考虑差分
设 g[j] = f[j] - f[j - 1]。
转移成功： f[i][j] < f[i - 1][j - 1] + (j - 1) * a + b
即：g[j] < (j - 1) * a + b。
可以据此二分 k。
转移后对 f 数组的影响：
$k$ 及以后： $f[i][j] = f[i - 1][j - 1] + (j - 1) * a + b
转移后对 g 数组的影响:
$k$ : $g[k] = (k - 1) * a + b
对应的 $g$ 数组的变化：
$k$ 前插入了一个 $(k - 1) * a + b$；后面的所有数都加了 $a$。
$Splay$ 可以轻松维护这些操作。（二分k，插入，区间加）
## 决策单调性优化DP
### 前置技能：~~四边形不等式~~ 打表
如果发现决策点单调递增，那么可以套用一下板子（注意:一定注意各种细节，比如对队列非空的特判）
**四边形不等式：相交优于包含**
- 对于 DP 式子为 $f(i) = \min_j f(j) + v(i,j)$ 来说，如果 $i \le j \le k \le l$ 时 $v(i,k) + v(j,l) \le v(i, l) + v(j, k)$，那么满足决策单调性。
- 二维：$f(l,r) = \min_m f(l,m) + f(m + 1, r) + v(l,r)$，其中 $v$ 满足上述性质，则 $g(l,r) \in [g(l,r - 1), g(l + 1, r)]$，$g$ 为决策点。然后 $O(n^3)$ 区间 DP 就可以优化到 $O(n^2)$ 了。
- 自己瞎证：比如可以根据转移函数凸性，依据定义证明。
一定要背熟板子啊！！！
### [SP9070 LIGHTIN - Lightning Conductor](https://www.luogu.com.cn/problem/SP9070)
### [P3515 [POI2011]Lightning Conductor](https://www.luogu.com.cn/problem/P3515)
### [P5503 [JSOI2016]灯塔](https://www.luogu.com.cn/problem/P5503)
### [P1912 [NOI2009]诗人小G](https://www.luogu.com.cn/problem/P1912)
### [T134955 shoes](https://www.luogu.com.cn/problem/T134955)
### 栈（单调队列）写法
```
/*
维护三元组单调队列<l, r, pos>，pos为[l,r]内的决策点。
由于有决策单调性，队列里的区间和决策点都是单调递增的。
此题型的大致过程如下：
*/
for (int i = 1; i <= n; ++i) {
if (队列非空 && 队头右端点比i小) 弹掉队头
else 修改队头的l
用队头计算f[i]
if (i -> n 不如 队尾决策点 -> n 优） continue;
while (队列非空 && i -> 队尾左端点 优于 队尾决策点 -> 队尾左端点） 弹队尾
if (队空） 添加节点(i, n, i)于队尾
else {
查找x = 队尾区间中 i占优势的第一个点（可能为r+1）
修改队尾右端点
新增节点(x, n, i)
}
}
```
Code：
```cpp
inline ll calc(int j, int i)//计算用j来转移i
...
//main()中
q[++rear] = (node){1, n, 1};
f[1] = ...
for (register int i = 2; i <= n; ++i) {
if (q[front + 1].l == q[front + 1].r) ++front;
else ++q[front + 1].l;
//调整最靠前的三元组的 l。注意判空三元组
register int pos = q[front + 1].pos;
f[i] = calc(pos, i);
pre[i] = pos;
//计算
//-------
//插入i
if (calc(i, n) >= calc(q[rear].pos, n)) continue;
//i更新无望，提前推出，防止出现空三元组
while (front < rear && calc(q[rear].pos, q[rear].l) >= calc(i, q[rear].l))
rear--;
//尝试用i弹掉后面的整块，注意判非空
if (front >= rear) {
q[++rear] = (node){i, n, i};
continue;
}
//i足够优秀，把三元组全部弹完了，就特判退出
int x = ...
/*
二分查找i占优势的最靠左的点，为x
*/
q[rear].r = x - 1;
q[++rear] = (node){x, n, i};
}
```
### 递归写法
对于一些**决策点的贡献都已知**前提下的问题，即状态有层次的情况，还有一种细节更少，更方便的方法。
对于状态 $(il, ir, jl, jr)$，其中 $il, ir$ 表示当前需要算的状态的区间；$jl, jr$ 表示当前区间对应的决策点区间。我们可以**暴力算出mid(il, ir)的决策点的位置，然后把决策点区间分裂成两段**，然后递归子问题。
```cpp
ll f[N], g[N];//f: 当前要算的状态；g：上一层的状态
inline void sol(int ql, int qr, int l, int r) {
if (ql > qr) return ;
int mid = (ql + qr) >> 1;
int pos = 0;
int limi = min(mid - 1, r);
f[mid] = inf;
for (register int i = l; i <= limi; ++i) {
ll tmp = g[i] + Query(i + 1, mid);
if (tmp < f[mid]) f[mid] = tmp, pos = i;
}
sol(ql, mid - 1, l, pos); sol(mid + 1, qr, pos, r);
}
inline void work() {
memset(f, 0x3f, sizeof(f));
f[0] = 0;
for (register int i= 1; i <= K; ++i) {
memcpy(g, f, sizeof(g));
memset(f, 0, sizeof(f));
sol(1, n, 0, n);
}
}
```
[L. Partially Free Meal](https://contest.ucup.ac/contest/1358/problem/7523)：
> 给序列 $a_i,b_i$，对每个 $k$，求长为 $k$ 的子序列 $p_i$ 使得
> $$\sum_{i=1}^k a_{p_i} + \max_{i=1}^k \{ b_{p_i} \}$$
> 最大。输出这 $n$ 个最大值。$n \le 2 \times 10^5, a_i,b_i \le 10^9