BZOJ 1537 [POI2005]Aut- The Bus

题目大意

给你网格图上的一堆点$( X , Y ) ( X \leq N , Y \leq M )$，每个点都有一个权值$ P _ i $，求从$ ( 1 , 1 ) $走到$ ( N , M ) $的最大权值和

数据结构优化DP.

这道题首先当然是要$ X \uparrow \to Y\uparrow$排个序，之后得到转移方程 $F_{i(X,Y)}=\max(F_{j(A,B)} + P_{i}) (A \leq X,B \leq Y,j \lt i)$ 如果暴力枚举当然是$O(N^2)$的了，所以需要优化。首先根据排序可知对于一个正在判断中的$i$，必定对于$\forall (j_{(A,B)},i_{(X,Y)})(j \lt i)$都有$A \leq X$。所以我们成功将二维限制转化为了一维限制。对于一维限制我们没办法直接保证，所以可以使用数据结构维护一下（such as 线段树），维护一下最大值就可以了。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,k,maxn[3000010],ls[3000010],rs[3000010],root,tot,ans,f[1000010];
struct stop{int x,y,p,id;}s[100010];
bool cmp(stop tx,stop ty)
{
	if(tx.y==ty.y) return tx.x<ty.x;
	return tx.y<ty.y;
}
void add(int &pos,int l,int r,int tx,int ty)
{
	if(!pos) pos=++tot;
	if(l==r) {maxn[pos]=ty;return;}
	int mid=(l+r)>>1;
	if(tx<=mid) add(ls[pos],l,mid,tx,ty);
	else add(rs[pos],mid+1,r,tx,ty);
	maxn[pos]=max(maxn[ls[pos]],maxn[rs[pos]]);
}
int query(int pos,int l,int r,int tx)
{
	if(!pos) return 0;
	if(r<=tx) return maxn[pos];
	int mid=(l+r)>>1,ret=0;
	ret=max(ret,query(ls[pos],l,mid,tx));
	if(tx>mid) ret=max(ret,query(rs[pos],mid+1,r,tx));
	return ret;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;++i) scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].p),s[i].id=i;
	sort(s+1,s+k+1,cmp);
	for(int i=1;i<=k;++i)
	{
		f[i]=query(root,1,n,s[i].x)+s[i].p;
		add(root,1,n,s[i].x,f[i]);
	}
	for(int i=1;i<=k;++i) ans=max(ans,f[i]);
	printf("%d\n",ans);
	return 0;
}