【HDU6447】YJJ's Salesman(dp+树状数组+离散)
YJJ's SalesmanTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2046 Accepted Submission(s): 768 Problem Description YJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination.
Input The first line of the input contains an integer T (1≤T≤10) ,which is the number of test cases.
Output The maximum of dollars YJJ can get.
Sample Input 1 3 1 1 1 1 2 2 3 3 1
Sample Output 3
Source |
【题意】
如果把左上角定为原点,那么它只能向右或向下或右下走,但是只有往右下走是可以拿到金钱的,问他最多能拿到多少金钱
【解题思路】
终于来补这题了qaq每天催眠自己做题是快乐的,补题是有趣的( 才怪:( )
因为点的个数实际上是1e5个,但是坐标有1e9,所以首先需要离散化,这里用结构存储横纵坐标,将点离散化到1e5*1e5个。
然后下面的题解应该还是挺清楚的,能够明白。
【代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
int y[maxn],n;
LL tree[maxn];
struct Node
{
int x,y,w;
}node[maxn];
bool cmp(Node a,Node b)
{
return (a.x==b.x)?a.y>b.y:a.x<b.x;
}
int lowbit(int x)
{
return x&(-x);
}
void update(int k,LL w)
{
while(k<=n)
{
tree[k]=max(w,tree[k]);
k+=lowbit(k);
}
}
LL query(int k)
{
LL ans=0;
while(k)
{
ans=max(ans,tree[k]);
k-=lowbit(k);
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(tree,0,sizeof(tree));
memset(node,0,sizeof(node));
memset(y,0,sizeof(y));
LL ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].w);
y[i]=node[i].y;
}
sort(y+1,y+1+n);
sort(node+1,node+1+n,cmp);
for(int i=1;i<=n;i++)
{
int index=lower_bound(y+1,y+1+n,node[i].y)-y;
LL tmp=query(index-1)+node[i].w;
ans=max(tmp,ans);
update(index,tmp);
}
printf("%lld\n",ans);
}
return 0;
}
推荐阅读