[笔记] [题解]斜率优化\(DP\)&洛谷P3195玩具装箱

原题链

斜率优化讲解

对于洛谷上的这道题,我们设\(sum[k] = \sum_{i=1}^kC[i]+1\)(可以把S数组视为\(C\)的前缀和),用\(dp[i]\)表示装好前\(i\)个玩具的最小费用,不是长度,那么我们可以得到转移方程:

\[dp[i]=min_{0\leq j<i}(dp[j]+(\sum_{k=j+1}^{i}C_k+i-j-1-L)^2)\\ dp[i]=min(dp[j]+(sum[i]-sum[j]-1+L)^2) \\ 令f[i]=sum[i]+i,可继续化简得: \\ dp[i]=min(dp[j]+(f[i]-f[j]-1-L)^2) \]

此时暴力进行\(DP\)是\(O(n^2)\)的,仍然要优化.

对于每一个\(dp[i]\)都是由一个\(j\)推到而来的,并且这个\(j\)是对于当前的\(i\)的最优决策.现在假设有\(j_1,j_2(1{\leq}j_1{<}j_2{<}i)\),并且决策\(j_2\)优于\(j_1\),那么就有

\[dp[j_1]+(f[i]-f[j_1]-1-L)^2 \geq dp[j_2]+(f[i]-f[j_2]-1-L)^2\\ 拆括号得\\ dp[j_1]+f[i]^2-2f[i](f[j_1]+1+L)+(f[j_1]+L+1)^2\geq dp[j_2]+f[i]^2-2f[i](f[j_2]+1+L)+(f[j_2]+L+1)^2\\ 化简可得:\\ 2f[i](f[j_2]+1+L)-2f[i](f[j_1]+1+L) \geq dp[j_2]+(f[j_2]+1+L)^2-(dp[j_1]+f[j_1]+1+L)^2\\ 即\\ 2f[i] \geq \frac{dp[j_2]+(f[j_2]+1+L)^2-(dp[j_1]+(f[j_1]+1+L)^2)}{f[j_2]-f[j_1]}\\ 令g[i]=(f[i]+L+1)^2,可得: 2f[i] \geq \frac{dp[j_2]+g[j_2]-(dp[j_1]+g[j_1])}{f[j_2]-f[j_1]} \]

那么也就是说如果有\(j_1,j_2\)满足这两个式子,那么\(j_2\)一定比\(j_1\)要更优.

那么为什么要叫斜率优化呢?其实我们观察最终得到的式子可以吧\(dp[i]+g[i]\)看做纵坐标,\(f[i]\)看做横坐标,那么这个式子其实就相当于\(k=\frac{{\Delta}y}{{\Delta}x}\),也就是一个一次函数的斜率表达式,当这个斜率\(k \leq 2f[i]\)时则\(j_2\)优于\(j_1\).

根据上面推出来的关系我们就可以用最优的决策来更新答案了,代码就是上面公式的翻译,加上一个单调队列

代码

#include <bits/stdc++.h>
using namespace std;
long long n,l;
long long sum[500010],f[500010],head,tail,q[50010],dp[500010],g[500010];
double slope(int x,int y){
	return (double)(dp[y] + g[y] - dp[x] - g[x]) / (f[y] - f[x]);
}
int main(){
	scanf("%lld%lld",&n,&l);
	for(int i = 1;i <= n;i++){
		scanf("%lld",&sum[i]);
		sum[i] += sum[i - 1];
		f[i] = sum[i] + i;
		g[i] = (f[i] + l + 1) * (f[i] + l + 1);
	}
	g[0] = (l + 1) * (l + 1);
	for(int i = 1;i <= n;i++){
		while(head < tail && slope(q[head],q[head + 1]) <= 2 * f[i])head++;
		dp[i] = dp[q[head]] + (f[i] - f[q[head]] - l - 1) * (f[i] - f[q[head]] - l - 1);
		while(head < tail && slope(q[tail],i) < slope(q[tail - 1],q[tail]))tail--;
		q[++tail] = i;
	}
	printf("%lld\n",dp[n]);
	return 0;
}