思路:

首先不难想到排序后dp,可是这样就\(O(n^2)\)超时了.

一开始想的是按照列从前往后做,然后给每一个之前的列维护一个单调队列.可是发现这样是\(O(m^3)\)的.

我们可以注意到一条性质:由于\(a,b>0\)时,\((a+b)^2>a^2+b^2\),且价值均\(>0\),所以路径上相邻两个点形成的矩形中不能存在别的点.

也就是说对于之前的每一列,只有最下面的才有用.

我们在扫的时候顺便记录一下这个就好了.

时间复杂度\(O(nm)\).

#include
#include
#include
#include
#include
using namespace std;

#define N 200010
#define M 1010
struct Pos{
	int x,y,lab;
	bool operator<(const Pos&B;)const{return x<=n;++i)scanf("%d%d",&P;[i].x,&P;[i].y),x[i]=P[i].x,y[i]=P[i].y,P[i].lab=i,scanf("%d",&w;[i]);
	sort(P+1,P+n+1);
	
	f[P[1].lab]=w[P[1].lab],g[1]=P[1].lab;
	for(i=2;i<=n;++i){
		f[P[i].lab]=-1<<30;
		for(j=1;j<=P[i].y;++j)if(g[j])f[P[i].lab]=max(f[P[i].lab],f[g[j]]+w[P[i].lab]-sqr(P[i].y-j)-sqr(P[i].x-x[g[j]]));
		g[P[i].y]=P[i].lab;
	}
	
	for(i=1;i<=n;++i)if(x[i]==m&&y;[i]==m)printf("%d",f[i]);
	return 0;
}