四边形不等式优化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
#endif

const 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表示能更新的那一段的开始位置, 结束位置一定是n
	int 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]所有的最优决策点都是0
	for (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
• 洛谷日报