斜率优化

高中的时候做过几道斜率优化的题目，不过一直没有搞的太懂。 这次填一下坑。 http://www.lydsy.com/JudgeOnline/problem.php?id=4518

Pine开始了从S地到T地的征途。从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。 Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。 Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。 帮助Pine求出最小方差是多少。 设方差是v，可以证明，v×m^{2是一个整数。为了避免精度误差，输出结果时输出v×m}2。

设每一天的路程为\(x_i\)，\(S=\sum_{i=1}^{n}x_i\) 所求即为： \[ans = m^2 \times \sum\limits_{i=1}^m \frac{(x_i - \frac{S}{m}) ^ 2}{m}\] 化简为： \[ans = m \times \sum\limits_{i=1}^m x_{i}^2 - S^2\] 因为\(S\)为定值，只需使\(\sum_{i=1}^{m}x_i\)最小即可 设\(f[i][j]\)表示前\(j\)短路在前\(i\)天分配的最小平方和 则\[f[i][j]=min(f[i-1][j-k]+(sum[j]-sum[j-k])^2) k=1..j\] 假设\(x>y\)，且\(j\)由\(x\)转移比从\(y\)转移更优，则 \[f[i-1][x]+(sum[j]-sum[x])^2\]

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long sum[3010]={};
long long f[3010]={};
long long g[3010]={};
long long q[3010]={};
long long fz(int x,int y)
{
	return g[x]-g[y]+sum[x]*sum[x]-sum[y]*sum[y];
}
long long fm(int x,int y)
{
	return sum[x]-sum[y];
}
int main()
{
	long long p;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&p);
		sum[i]=sum[i-1]+p;
	}
	memset(f,0x7f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=m;i++)
	{
		memcpy(g,f,sizeof(f));
		memset(q,0,sizeof(q));
		int head=0,tail=0;
		for(int j=1;j<=n;j++)
		{
			while(head<tail&&fz(q[head+1],q[head])<2*sum[j]*fm(q[head+1],q[head])) head++;
			f[j]=min(f[j],g[q[head]]+(sum[j]-sum[q[head]])*(sum[j]-sum[q[head]]));
			while(head<tail&&(fz(q[tail],q[tail-1])*fm(j,q[tail])>fz(j,q[tail])*fm(q[tail],q[tail-1]))) tail--;
			q[++tail]=j;
		}
	}
	printf("%lld\n",f[n]*m-sum[n]*sum[n]);
	return 0;
}

http://www.lydsy.com/JudgeOnline/problem.php?id=1597

农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.

首先，我们发现，如果一个矩形能完全包括另一个矩形，那么另一个矩形就是完全没有意义的。 我们可以通过排序用一个栈把所有被包括的矩形去掉，然后剩下的矩形按照长度不下降排序的话，长度如果不下降，宽度一定不上升。 于是我们得到了一个显然的动态规划方程：\[f_i=\min\limits_{j=1}^{i-1}(f_i,f_j+a_i \times b_{j+1})\] 这是一个\(O(n^2)\)的算法，需要优化。 对于\(x>y\)，如果\(x\)优于\(y\) 即\[f_x+a_i \times b_{x+1}\]

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long sum[3010]={};
long long f[3010]={};
long long g[3010]={};
long long q[3010]={};
long long fz(int x,int y)
{
	return g[x]-g[y]+sum[x]*sum[x]-sum[y]*sum[y];
}
long long fm(int x,int y)
{
	return sum[x]-sum[y];
}
int main()
{
	long long p;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&p);
		sum[i]=sum[i-1]+p;
	}
	memset(f,0x7f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=m;i++)
	{
		memcpy(g,f,sizeof(f));
		memset(q,0,sizeof(q));
		int head=0,tail=0;
		for(int j=1;j<=n;j++)
		{
			while(head<tail&&fz(q[head+1],q[head])<2*sum[j]*fm(q[head+1],q[head])) head++;
			f[j]=min(f[j],g[q[head]]+(sum[j]-sum[q[head]])*(sum[j]-sum[q[head]]));
			while(head<tail&&(fz(q[tail],q[tail-1])*fm(j,q[tail])>fz(j,q[tail])*fm(q[tail],q[tail-1]))) tail--;
			q[++tail]=j;
		}
	}
	printf("%lld\n",f[n]*m-sum[n]*sum[n]);
	return 0;
}

http://www.lydsy.com/JudgeOnline/problem.php?id=3156

题目

依然是斜率优化。 先看最普通的动态规划，设状态\(f[i]\)代表最后一个守护塔放在\(i\)处的最小花费。 于是动态规划方程：\[f[i]=\min\limits_{j=i+1}^{n}(f[i],f[j]+\frac{(j-i-1)\times(j-i)}{2}+a[i])\] 当\(x2 \times i+1\) 这样我们就可以维护一个上凸壳。 （其实在单调队列中的大于小于情况最多就有四种，感觉枚举一下就可以了...）

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[1000010]={};
long long f[1000010]={};
int q[1000010]={};
long long fz(long long x,long long y)
{
	return 2*f[x]+x*x-2*f[y]-y*y;
}
long long fm(long long x,long long y)
{
	return x-y;
}
int main()
{
	scanf("%d",&n);
	a[0]=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	f[n]=a[n];
	int head=0,tail=0;
	q[0]=n;
	for(long long i=n-1;i>=0;i--)
	{
		while(head<tail&&fz(q[head+1],q[head])<(2*i+1)*fm(q[head+1],q[head])) head++;
		long long j=q[head];
		f[i]=f[j]+(j-i-1)*(j-i)/2+a[i];
		while(head<tail&&fz(q[tail],q[tail-1])*fm(i,q[tail])<fm(q[tail],q[tail-1])*fz(i,q[tail])) tail--;
		q[++tail]=i;
	}
	printf("%lld",f[0]);
	return 0;
}