自动搬运

查看原文

来自洛谷，原作者为

	Sakits **

搬运于2025-08-24 21:56:01，当前版本为作者最后更新于2018-03-11 21:33:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

https://sakits.com/bzoj1560/

题解

这题网上题解大都是$O(nm)$的做法，实际上用斜率优化可以做到$O(m^2)$，可貌似只有lichangdongtw大爷提到了斜率优化，但是没细讲，那我就详细说一下吧...虽然会$O(nm)$肯定就会斜率优化了吧qaq

首先先说一下$O(nm)$的做法。设$f(i)$为走到第$i$个点时的最大收益，显然有：

朴素的转移当然是$O(n^2)$的，但是我们可以发现每一列上能转移的点行数大的一定比行数小的更优，因为：

所以对于每一列我们只需要保存可转移点中行数最大的点，从这些点转移就好了，那么转移复杂度是$O(m)$的，总复杂度$O(nm)$，可以卡过去。

观察一下方程，平方展开后有一些$i$和$j$的乘积，可以联想到斜率优化。这题如果使用斜率优化的话，可以桶排后做到$O(m^2)$，但是我们也可以改变一下状态表示，不需要桶排。

设$f(i)(j)$为走到$(i,j)$上的点的最大收益，枚举每一列最底下的点来转移，因为我们确定了转移点的列就能确定行，为了写方程更简单一些，我省略第一维来写方程，设$pos_i$为第$i$列上当前能转移的点的最大行数，$x$为当前点的行数：

设$j<k$，且从$k$转移比从$j$转移优，则有：

然后就可以斜率优化了...注意横坐标相同时斜率要设为-inf

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1010, inf=1e9;
const double eps=1e-6;
int n, m, x, y, z;
int f[maxn][maxn], w[maxn][maxn], pos[maxn], dis[maxn], q[maxn];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}
inline double xl(int x, int y){return (x==y)?-inf:1.0*(f[pos[x]][x]-f[pos[y]][y]-dis[x]+dis[y]-x*x+y*y)/2/(y-x);}
int main()
{
	read(n); read(m);
	for(int i=1;i<=n;i++) read(x), read(y), read(w[x][y]);
	memset(f, 200, sizeof(f));
	f[1][1]=w[1][1]; pos[1]=1; w[1][1]=0; 
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=m;j++) dis[j]=(pos[j]!=0)*(pos[j]-i)*(pos[j]-i);
		int l=1, r=0;
		for(int j=1;j<=m;j++)
		{
			if(pos[j]) 
			{
				while(l<r && xl(q[r-1], q[r])>xl(q[r], j)-eps) r--;
				q[++r]=j; 
			}
			if(w[i][j])
			{
				while(l<r && xl(q[l], q[l+1])-eps<j) l++;
				f[i][j]=f[pos[q[l]]][q[l]]-dis[q[l]]-(q[l]-j)*(q[l]-j)+w[i][j];
				pos[j]=i; dis[j]=0;
				while(l<r && xl(q[r-1], q[r])>xl(q[r], j)-eps) r--;
				q[++r]=j; 
			}
		}
	}
	printf("%d\n", f[m][m]);
}