四边形不等式优化DP

四边形不等式内容

TODO

[HNOI2008]玩具装箱

解析

• 满足四边形不等式，决策具有单调性. 对于两个位置$i,j$, 对应的最优决策点一定有 $opt[i]<=opt[j]$
• 代码实现
  • 需要有一个队列，这里我们使用c++里的双端队列($deque$). 因为需要在队尾插入和弹出，队首弹出的操作.
  • 初始化时，队列里只有一个元素, 比如本题中区间$[1,n]$, 决策点为$0$. 这个对所有的位置$[1,n]$都是合法的一个决策
  • 每次插入决策$x$的时候，从队尾开始判断，如果当前的节点的区间的开始位置决策$x$更优，就弹出队尾，一直这么做.
  • 接上一步, 于是就找到了一个节点(当前队尾): 对应的区间开始位置$x$不优，结束位置$x$更优。所以存在一个临界点，我们二分就是要找这么一个位置$pos$. $[pos,n]$这部分$x$更优，其他位置不变.
  • 主函数循环部分，我们维持队列的区间都是还未确定最优决策的部分。
  • 主函数循环部分，当循环到位置$i$时候，由于我们已经考虑过小于$i$的所有决策，因此对于位置$i$，队首的决策就是位置$i$的最优决策.

代码实现

#include <bits/stdc++.h>
using namespace std;#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endifconst int N = 5e4 + 5;typedef long long LL;int n, L;
// 原数组，以及前缀和
vector<LL> a, sum;
// dp[i]: 前i个玩具的最小费用. dp[i] = min(dp[j] + (s[i] - s[j] + i - j - 1 - L)^2), 0 <= j < i
vector<LL> dp;
// f[i]的最优决策点是谁, 也就是f[i]取得最小值的时候对应的上面的式子中的j. opt[i] = j.
vector<int> op;struct Node {int l, r, c;Node(int _l, int _r, int _c): l(_l), r(_r), c(_c){}
};// 存在插入队尾,弹出队首,弹出队尾三种操作,因此我们使用deque
deque<Node> q;// dp方程: f[j] = f[i] + (x - L) ^ 2
inline LL val(int j, int i) {LL s = sum[i] - sum[j] + i - j - 1 - L;return dp[j] + 1LL * s * s;
}// 用决策x更新
void insert(int x) {// pos表示能更新的那一段的开始位置, 结束位置一定是nint pos = n + 1; // 临界点// 找到x能更新的队列，一定是末尾的一段// 队列里队尾的元素. 看决策x是否是更优的决策. 满足'<='意味着x更优while (q.size() && val(x, q.back().l) <= val(q.back().c, q.back().l)) {pos = q.back().l; // 更新pos: [q,back().l, q.back().r] 这一段肯定x更优q.pop_back();}// 找到了这个区间. 这个区间的右边界x更优,左边界x不优秀. 我们二分寻找临界点在哪里if (q.size() && val(x, q.back().r) <= val(q.back().c, q.back().r)) {int l = q.back().l, r = q.back().r;while (l < r) {int mid = l + r >> 1;if (val(x, mid) <= val(q.back().c, mid)) r = mid; // 对于mid这个点, x的决策更优, 临界点在左边 -> [l, mid]else l = mid + 1; // mid这个点,x不优. 那么临界点在右半部分 -> [mid + 1, r]}// 结束循环时,r是使x成为最优决策的一段的起始位置pos = r;q.back().r = r - 1;}// 说明存在某些位置x的决策比当前队列的优. 也就是进入过上面的代码.if (pos != n + 1) q.push_back(Node(pos, n, x));
}int main() {cin >> n >> L;a = sum = dp = vector<LL>(n + 1, 0);op = vector<int>(n + 1, 0);for (int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];q.push_back(Node(1, n, 0)); // 一开始队列只有一个元素，表示[1, n]所有的最优决策点都是0for (int i = 1; i <= n; i++) {// 队头的决策点就是当前i的最优决策int opt = q.front().c;dp[i] = val(opt, i);op[i] = opt;// 弹出已经无用的决策if (q.front().r == i) q.pop_front();q.front().l = i + 1;// 插入当前决策,并用决策i去更新 [i + 1, n]的最优决策insert(i);}cout << dp[n] << endl;return 0;
}

参考资料

• OIWIKI
• 洛谷日报