BZOJ1560:[JSOI2009]火星藏宝图 dp

思路:

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

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

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

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

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

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

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 200010
#define M 1010
struct Pos{
	int x,y,lab;
	bool operator<(const Pos&B)const{return x<B.x||(x==B.x&&y<B.y);}
}P[N];

int w[N],f[N],g[M],x[N],y[N];
inline int sqr(int x){return x*x;}

int main(){
	int n,m;scanf("%d%d",&n,&m);register int i,j;
	
	for(i=1;i<=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;
}