大致题意： 一张\(m\times m\)的图上有\(n\)个点，每个点有一个收益。每次只能从一个点到右下方的另一个点，代价是两点间距离的平方。求从\((1,1)\)到\((n,m)\)收益减代价的最大值。
暴力
对于每一个关键点，显然可以枚举所有在它左上方的点作为到达它的前一个点。
若之前出现过位于同一列的两点（更多点也是同理的），设它们分别为\((x,t),(y,t)(x<y)\)，且当前点为\((i,j)\)。然后考虑以下两种方案的代价：
- 从\((x,t)\)直接到\((i,j)\)：\((x-i)^2+(t-j)^2\)。
- 从\((x,t)\)到\((y,t)\)再到\((i,j)\)：\((x-y)^2+(y-i)^2+(t-j)^2\)。（其实此处还有\(a_{y,t}\)的收益，实际代价要更小）
换元，令\(x-y=p,y-i=q\)，同时约去两式中的\((t-j)^2\)，显然有：
\[(x-i)^2=(p+q)^2=p^2+q^2+2pq>p^2+q^2 \]
也就是说，对于同一列从最下方的点转移必然是最优的。
于是我们就得到了一个\(O(nm)\)的暴力\(DP\)，这个相信大家都会写的吧。。。
而且\(O(nm)\)是跑不满的，实测跑得飞快。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define M 1000
#define Gmax(x,y) (x<(y)&&(x=(y)))
#define Sqr(x) ((x)*(x))
using namespace std;
int n,m,a[M+5][M+5],f[M+5][M+5],g[M+5],w[M+5];
class FastIO
{
private:
#define FS 100000
#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
#define D isdigit(c=tc())
char c,*A,*B,FI[FS];
public:
I FastIO() {A=B=FI;}
Tp I void read(Ty& x) {x=0;W(!D);W(x=(x<<3)+(x<<1)+(c&15),D);}
}F;
int main()
{
RI i,j,k,x,y;for(F.read(n),F.read(m),i=1;i<=n;++i) F.read(x),F.read(y),F.read(a[x][y]);//读入点
for(i=1;i<=m;++i) g[i]=-1e9;for(i=1;i<=m;++i) for(j=1;j<=m;++j) if(a[i][j])//只处理关键点
{
for(f[i][j]=i==1&&j==1?0:-1e9,k=1;k<=j;++k) Gmax(f[i][j],g[k]-Sqr(i-w[k])-Sqr(j-k));//枚举之前每一列DP
g[j]=(f[i][j]+=a[i][j]),w[j]=i;//更新当前点所在列信息
}return printf("%d",f[m][m]),0;//输出答案
}