【决策单调性优化DP】玩具装箱

题意

有\(n\)个玩具装箱，每个玩具长度为\(c_i\)，将它们按顺序装箱，即划分若干段。
如果要在一个箱子里装编号为\(i\sim j\)的玩具，则箱子长度为\(l=j-i+\sum_{k=i}^{j}c_k\)。
一个长度为\(l\)的箱子费用为\(P=(l-L)^2\)，求最少费用。

思路

设\(f_i\)为前\(i\)个玩具装箱的最少费用。
\(f_i=min_{j=1}^{i-1}{f_j+w_{j+1,i}}\)
其中\(w_{i,j}\)为玩具\(i\sim j\)装箱的费用。
可以发现这个\(w\)是满足四边形不等式的，即\(\forall i\leq j,w_{i,j}+w_{i+1,j+1}\leq w_{i+1,j}+w_{i,j+1}\)，即满足决策单调性。
使用二分法即可。

代码

#include <cstdio>
#define int long long

struct node {
	int l, r, p;
}s[50001];
int n, l, top, now;
int f[50001], sum[50001];

int val(int j, int i) {
	return f[j] + (i - j - 1 + sum[i] - sum[j] - l) * (i - j - 1 + sum[i] - sum[j] - l);
}

int find(int p) {
	int l = s[top].l, r = n;//在l,r之间寻找决策的转折点p，即p->mid <= s[top].p->mid
	while (l < r) {
		int mid = l + r >> 1;
		if (val(p, mid) > val(s[top].p, mid))
			l = mid + 1;
		else
			r = mid;
	}
	return l;
}

int find1(int p) {
	int l = 1, r = top;
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (s[mid].l <= p)
			l = mid;
		else
			r = mid - 1;
	}
	return l;
}

signed main() {
	scanf("%lld %lld", &n, &l);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &sum[i]), sum[i] += sum[i - 1];
	s[++top] = (node){1, n, 0};
	for (int i = 1; i <= n; i++) {
		f[i] = val(s[find1(i)].p, i);
		while (top && i < s[top].l && val(i, s[top].l) < val(s[top].p, s[top].l))
			top--;
		int u = find(i);
		if (val(i, u) > val(s[top].p, u)) continue;//找不到
		s[top].r = u - 1;
		if (u <= n)
			s[++top] = (node){u, n, i};//插入新决策区间
	}
	printf("%lld", f[n]);
}

【决策单调性优化DP】玩具装箱

原文：https://www.cnblogs.com/HSZGB/p/14602288.html