洛谷P3915 斜率优化线性dp

题意：

有$n$个玩具，每个玩具有一个价值$c_i$，需要把这个玩具分成任意段，使得分割总代价最小。每分割出一段$[l,r]$，代价是$(r-l+{\sum }_{i=l}^r{c}_i-L{)}^2$

方法：

一个经典的线性$dp$：

设$dp[i]$为分割前$i$个的最小代价，那么$dp[i]=max(dp[j]+cost(j+1,i)),j\in [0,i-1]$，时间复杂度$O(n^2)$

将$cost$展开，得到

$$dp[i]=min(dp[j]+(i-j-1+getsum(j+1,i)-L-1{)}^2)$$

将$getsum(l,r)$以前缀和形式展开

$$dp[i]=min(dp[j]+(i-j-1+sum[i]-sum[j]-L-1{)}^2)$$

将$i,j$分类，并且将常数项归入任意一类，这里将常数归入$j$类

$$dp[i]=min(dp[j]+((i+sum[i])-(j+sum[j]+L+1){)}^2)$$

令$a[i]=i+sum[i],b[j]=j+sum[j]+L+1$

$$dp[i]=min(dp[j]+(a[i]-b[j]{)}^2)$$

完全平方展开

$$dp[i]=min(dp[j]+a[i{]}^2+b[j{]}^2-2\ast a[i]\ast b[j])$$

假设$j$就是我们找到的最佳决策点，那么

$$dp[i]=dp[j]+a[i{]}^2+b[j{]}^2-2\ast a[i]\ast b[j]$$

将$j$分离，一般地，应该是分离从哪里转移来的项

$$2\ast a[i]\ast b[j]+dp[i]-a[i{]}^2=dp[j]+b[j{]}^2$$

令$b[j]=x$，右边所有的（即分出来的$j$）$dp[j]+b[j{]}^2=y$得到

$$l:2\ast a[i]\ast x+dp[i]-a[i{]}^2=y$$

这是一个截距不确定的一次函数，我们将点$(k,dp[k]),k\in [0,i-1]$描在坐标轴上，因为$dp[i]$肯定从$j\in [0,i-1]$转移来，那么他必然经过其中一个点，我们需要让$dp[i]$最小，这里就等价于让截距$dp[i]-a[i{]}^2$最小，那么我们只需要维护描的点的下凸壳，$l$要选择一点经过，那么能使$l$的截距最小的点一定是下凸壳内的。同理，如果求的是$max$，需要维护一个上凸壳。

那么下凸壳哪个点是符合条件的呢？应该是凸包内第一对斜率$\ge k_l$的点对$(P_i,P_{i+1})$的第一个点，因为要使多边形上的某个点最近某条直线，那么这个点相关的两条线段的所在直线的斜率应该是一个比$k_l$大，一个比$k_l$小的，维护的是下凸壳，保证了斜率递增，所以上述的点对的第一个点$P_i$就是要找的点，又因为恰好下凸壳内的相邻点对斜率递增，所以我们可以单调队列维护他，我们要的一定是上一次用的后面的。

另外，我们推出了一个转移方程是

$$2\ast a[i]\ast b[j]+dp[i]-a[i{]}^2=dp[j]+b[j{]}^2$$

单调队列的头即最佳决策点$j$，此时可以直接通过这个方程推出$dp[i]$，同时转移方程原来还满足

$$dp[i]=max(dp[j]+cost(j+1,i))$$

也可以使用这个递推

需要注意的是：

（1）描的点是$(x,y)$，而不是$(i,dp[i])$

（2）可能$[1,i]$为一段，也就是从$0$转移而来，所以一开始要将$0$构成的点对放入队列

#include
#define ll long long
using namespace std;

int n,c[50005],L,q[50005];
ll sum[50005],dp[50005];

inline ll x(int k)
{
	return k+sum[k]+L+1;
}

inline ll y(int k)
{
	return dp[k]+x(k)*x(k);
}

inline double k(int temp1,int temp2)
{
	return 1.0*(y(temp2)-y(temp1))/(x(temp2)-x(temp1));
}

inline ll cost(int l,int r)
{
	auto getsum=[&](int l,int r){return sum[r]-sum[l-1];};
	return (r-l+getsum(l,r)-L)*(r-l+getsum(l,r)-L);
}

int main()
{
	//单调队列记录的是(i,dp[i])的i，而不是(x,y)
	//记录这个可以获知(x,y)，但只记录(x,y)无法获得j，需要多加一个位置在向量中
	//如果记录的是点对，0对应的点对是(0,(L+1)^2)，不是(0,0)
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&sum[i]);
		sum[i]+=sum[i-1];
	}
	for(int i=1,sta=1,en=1;i<=n;i++)
	{
		while(en-sta+1>=2&&k(q[sta],q[sta+1])<2.0*(i+sum[i])) sta++;
		int j=q[sta]; dp[i]=dp[j]+cost(j+1,i);
		while(en-sta+1>=2&&k(q[en],q[en-1])>k(i,q[en])) en--;
		q[++en]=i;
	}
	cout<<dp[n];
	return 0;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49