以下为 DP 的优化。
正难则反。考虑计算不合法方案。一个方案不合法一定存在一个主食，使得该主食在多于一半的方法中出现。
枚举这个“超标”的主食 \(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：
各种卡常。
仔细观察朴素多重背包的转移方程：
其中 \(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;
}
}
}
按照 \(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\) 前: 不变。
\(k\) 及以后： \(f[i][j] = f[i - 1][j - 1] + (j - 1) * a + b\)
转移后对 \(g\) 数组的影响:
\(k\) 前：不变。
\(k\) : \(g[k] = (k - 1) * a + b\)
\(k\) 后： \(g[j] = g[j - 1] + a\)。
对应的 \(g\) 数组的变化：
\(k\) 前插入了一个 \((k - 1) * a + b\)；后面的所有数都加了 \(a\)。
\(Splay\) 可以轻松维护这些操作。（二分k，插入，区间加）
如果发现决策点单调递增，那么可以套用一下板子（注意:一定注意各种细节，比如对队列非空的特判）
一定要背熟板子啊！！！
/*
维护三元组单调队列<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：
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)的决策点的位置，然后把决策点区间分裂成两段，然后递归子问题。
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);
}
}
暂时没时间写了。
主要思想是：不管它的“恰好K个”限制，但是每选一个就罚它一点代价，并记录它实际选了几个，根据实际选了几个来二分。
一般的理解是上/下凸函数，二分斜率切凸包。
另一种理解（见DP凸优化/WQS二分/带权二分
）：上/下凸函数，二分斜率，平移导数，移动导数“零点”。
注意几点：
假设是上凸函数求最大，那么我们二分一个斜率 \(k\)，应该满足 \(f(x) = k * x + b(x)\)，而我们可以比较容易求出最大的 \(b(x)\)，（不是求最大的 \(f(x)\)），然后根据 \(b(x)\) 和 \(x\) 可以反推出 \(f(x)\).因为这里是反推，所以虽然斜率是 \(k\)，我们却让每个数都减去 \(k\)，最终算 \(f(x)\) 的时候再加 \(k\)。
最好在结构体比大小的时候搞一个第二关键字:\(ct(x)\)，在 \(val\) 相同的时候比较 \(ct\).
最终反推的时候要减去 \(need * mid\)，而不是 \(res.ct * mid\)！
原文：https://www.cnblogs.com/JiaZP/p/13322285.html