Description：

给一个 $n\times n$ 网格图，两个点间距离是欧几里得距离的平方，到一些点会获得一些价值，从左上角走到右下角，最大化价值 $-$ 总距离。

$1\leqslant n\leqslant 1000,1\leqslant m\leqslant 2\times 10^5$

Solution：

首先由于所有价值为正， $(a+b)^2\geqslant a^2+b^2$ ，所以如果一行一行转移的话，对于每一列的点最下面那一个一定是最优的，那么我们单个决策点的决策个数就只有 $O(n)$ 个了，于是有了一个 $O(nm)$ 的做法。

考虑继续优化，设 $f[i][j]$ 表示到了第 $(i,j)$ 这个位置的最大值， $pos[j]$ 表示第 $j$ 列的最下面那一个的横坐标，转移方程为： $$ f[i][j]=\max(f[pos[j']][j']-(i-pos[j'])^2-(j-j')^2)+w[i][j] $$ 看上去似乎不是很好优化但是斜率优化的本质是 $f[i]=\max/\min(x(j)\times a(i)+y(j)\times b(i)+z(j))+c(i)$ ，于是就可以斜率优化了。化一下式子就是： $$ f[i][j]+i^2+j^2-w[i][j]=2i\times pos[j']+2j\times j'+f[pos[j']][j']-j'^2-pos[j']^2 $$ 其中： $x[i]=pos[i],$ $y[i]=i,$ $z[i]=f[pos[i]][i]-i^2-pos[i]^2,$ $a[i][j]=2i,$ $b[i][j]=2j,$ $c[i][j]=w[i][j]-i^2-j^2$ 。 $$ \begin{align} f[i]&[j]=x[j']\times a[i][j]+y[j']\times b[i][j]+z[j']+c[i][j]\\ \Longrightarrow y[j']&=-\frac {a[i][j]}{b[i][j]}x[j']+\frac{f[i][j]-z[j']-c[i][j]}{b[i][j]}\\ \end{align} $$ 但是这样会发现做不了，因为 $b[i][j]=2j$ ，后面那个没法处理，但是我们可以把 $x$ 和 $y$ 换一下，即： $$ \begin{align} f[i]&[j]=y[j']\times a[i][j]+x[j']\times b[i][j]+z[j']+c[i][j]\\ \Longrightarrow y[j']&=-\frac {b[i][j]}{a[i][j]}x[j']+\frac{f[i][j]-z[j']-c[i][j]}{a[i][j]}\\ \end{align} $$ 这时由于在一行中 $a[i][j]=2i$ ，所以就可以把 $-\frac{z[j']}{2i}$ 放到左边，于是就是一个可以斜率优化的形式了。

斜率单调递减， $x$ 单调递增，要让截距最大，所以用单调队列维护上凸壳即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1010

int val[MAXN][MAXN];

int pos[MAXN];

int q[MAXN],head,tail;

long long f[MAXN][MAXN];

long double a(int i,int j){return 2.0 * i;}

long double b(int i,int j){return 2.0 * j;}

long double c(int i,int j){return val[i][j] - 1.0 * i * i - 1.0 * j * j;}

long double z(int i,int k){return f[pos[k]][k] - 1.0 * k * k - 1.0 * pos[k] * pos[k];}

long double yy(int i,int k){return pos[k] + z(i,k) / 2 / i;}

long double xx(int i,int k){return k;}

long double slope(int i,int a,int b){if(a == b)return 100000000;return (yy(i,a) - yy(i,b)) / (xx(i,a) - xx(i,b));}

int main()

{

	scanf("%d%d",&m,&n);

	int x,y,v;

	memset(val,0xc0,sizeof(val));

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&x,&y,&v);

		val[x][y] = v;

	}

	memset(f,0xc0,sizeof(f));

	f[1][1] = val[1][1];

	for(int i = 1;i <= n;++i)

	{

		head = 1;tail = 0;

		int last = 0;

		for(int j = 1;j <= n;++j)

		{

			if(pos[j] != 0)

			{

				while(head < tail && slope(i,j,q[tail]) >= slope(i,q[tail],q[tail - 1]))--tail;

				q[++tail] = j;

			}

			if(val[i][j] != 0xc0c0c0c0)

			{

				while(head < tail && slope(i,q[head],q[head + 1]) * a(i,j) >= -b(i,j))++head;

				if(head <= tail)

				{

					f[i][j] = (long long)(pos[q[head]] * 2 * i + z(i,q[head]) + xx(i,q[head]) * b(i,j) + c(i,j));

				}

				pos[j] = i;

				while(head < tail && slope(i,j,q[tail]) >= slope(i,q[tail],q[tail - 1]))--tail;

				q[++tail] = j;

			}

		}

	}

	cout << f[n][n] << endl;

	return 0;

}