自动搬运

查看原文

来自洛谷，原作者为

	greenheadstrange 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:48:55，当前版本为作者最后更新于2019-06-10 22:17:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很容易想到O（nm）的DP但是一看m和n的范围10^9，GG

再一看k的范围10^5，便想到离散化一下

//本蒟蒻是用map来离散化的，但是推荐dalao们还是用lower_bound比较好
map<int,int>mpx,mpy;
for(int i=1;i<=k;i++){
	scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].s);
	x[i]=a[i].x;
	y[i]=a[i].y;
	}	
x[0]=y[0]=1;
sort(x,x+k+1);
sort(y,y+k+1);
mpx[x[0]]=++nx;
mpy[y[0]]=++ny;	
for(int i=1;i<=k;i++){
	if(x[i]!=x[i-1])mpx[x[i]]=++nx;
	if(y[i]!=y[i-1])mpy[y[i]]=++ny;
}
for(int i=1;i<=k;i++)a[i].x=mpx[a[i].x],a[i].y=mpy[a[i].y];

此时的复杂度瞬间降到了O（k^2）但是只有40分，怎么办？

不要慌，先将动态转移方程写出来看看^_^

设f[i]表示走到点i的最大值

将数组a以横坐标作为第一关键字，纵坐标作为第二关键字排序后

f[i]=max(f[j])+a[i].s(其间a[j].y<=a[i].y)

亲爱的童鞋们，看到这里是不是想到了什么优化？

树状数组

sort(a+1,a+k+1,cmp);
for(int i=1;i<=k;i++){		
	f[i]=ask(a[i].y)+a[i].s;	
	modify(a[i].y,f[i]);	
}	

下面是本蒟蒻的丑代码：

#include<bits/stdc++.h>
using namespace std;
const int A=500005;
map<int,int>mpx,mpy;
struct note{
	int x,y,s;
}a[A];
int n,m,k,ans,x[A],y[A],c[A*4],f[A],nx,ny;
bool cmp(const note&aa,const note&bb){//以横坐标作为第一关键字，纵坐标作为第二关键字排序
	return (aa.x==bb.x?aa.y<bb.y:aa.x<bb.x);
}
///////////////////////////////树状数组 
int lowbit(int x){return x&(-x);}//lowbit操作 
void modify(int x,int k){//单点修改 
	for(int i=x;i<=ny;i+=lowbit(i))c[i]=max(c[i],k);
}
int ask(int x){//区间查询 
	int maxx=0;
	for(int i=x;i;i-=lowbit(i))maxx=max(maxx,c[i]);
	return maxx;
}
///////////////////////////////
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].s);
		x[i]=a[i].x;
		y[i]=a[i].y;
	}
	///////////////////////////////离散化 
	x[0]=y[0]=1;
	sort(x,x+k+1);
	sort(y,y+k+1);
	mpx[x[0]]=++nx;
	mpy[y[0]]=++ny;
	for(int i=1;i<=k;i++){
		if(x[i]!=x[i-1])mpx[x[i]]=++nx;
		if(y[i]!=y[i-1])mpy[y[i]]=++ny;
	}
	for(int i=1;i<=k;i++)a[i].x=mpx[a[i].x],a[i].y=mpy[a[i].y];
	///////////////////////////////
	
	///////////////////////////////DP 
	sort(a+1,a+k+1,cmp);
	for(int i=1;i<=k;i++){		
		f[i]=ask(a[i].y)+a[i].s;	
		modify(a[i].y,f[i]);	
	}	
	for(int i=1;i<=k;i++)ans=max(ans,f[i]);
	///////////////////////////////
	printf("%d",ans);
	return 0;
}

结束语：这道题并不难DP+树状数组，但是本蒟蒻却毒瘤了一个小时，结果是粗心将k与n混用了，在此，本蒟蒻提醒您：

代码千万条，细心第一条。

代码不规范，毒瘤两行泪。