http://www.lydsy.com/JudgeOnline/problem.php?id=1537
朴素的转移:dp[i][j]=max(dp[i][j-1],dp[i-1][j])+p[i][j]
树状数组优化
按x排序,离散化y
枚举,排序保证x,树状数组查询y
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 100001 #define lowbit(x) x&-x int c[N]; struct node
{
int x,y,p;
}e[N]; int tot,has[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void change(int x,int y)
{
while(x<=tot)
{
c[x]=max(c[x],y);
x+=lowbit(x);
}
} int query(int x)
{
int mx=;
while(x)
{
mx=max(mx,c[x]);
x-=lowbit(x);
}
return mx;
} bool cmp(node p,node q)
{
if(p.y!=q.y) return p.y<q.y;
return p.x<q.x;
} int main()
{
int n,m,k;
read(n); read(m); read(k);
for(int i=;i<=k;++i)
{
read(e[i].x);
read(e[i].y);
read(e[i].p);
has[i]=e[i].x;
}
sort(has+,has+k+);
tot=unique(has+,has+k+)-has-;
sort(e+,e+k+,cmp);
int tmp,pos; int ans=;
for(int i=;i<=k;++i)
{
pos=lower_bound(has+,has+tot+,e[i].x)-has;
tmp=e[i].p+query(pos);
ans=max(ans,tmp);
change(pos,tmp);
}
cout<<ans;
}