HDU 6447 YJJ’s Salesman （树状数组 + DP + 离散）
标签：str one play turn pen bre 一个 alt bool
题意：
二维平面上N个点，从（0，0）出发到(1e9，1e9），每次只能往右，上，右上三个方向移动，
该N个点只有从它的左下方格点可达，此时可获得收益。求该过程最大收益。
分析：我们很容易就可以想到用DP,假设这个位置是相对上一个位置的方向而来，但是复杂度达到N^2 ，这样是不行的；
我们可以利用坐标的信息，将所有的点离散化后，以x优先按小到大排序，按y按大到小排序，这时维护一个DP(i) ,表示第I列的最值。
j=0→i?1j=0→i?1
dp[i]←max(dp[i[,dp[j]+val)dp[i]←max(dp[i[,dp[j]+val)
因为x已经按从小到大排好序了，y也是从大到小更新的，故保证了可达性。
对于每次更新，可以用线段树或者树状数组维护最大值，此时算法复杂度O(NlogN)
#includeusing namespace std;
int n,hashx[100001],hashy[100001],dp[100001],tree[100001];
struct no
{
int x,y,w;
}a[100001];
bool cmp(no a, no b)
{
if(a.x==b.x)
return a.y>b.y;
return a.xb.x;
}
//离散化
void init( )
{
for(int i=1 ; i)
{
hashx[i] = a[i].x;
hashy[i] = a[i].y;
}
sort(hashx+1,hashx+1+n);
sort(hashy+1,hashy+1+n);
int cntx = unique(hashx+1,hashx+1+n)-hashx;
int cnty = unique(hashy+1,hashy+1+n)-hashy;
for(int i=1 ; i)
{
a[i].x = lower_bound(hashx+1,hashx+1+cntx,a[i].x)-hashx;
a[i].y = lower_bound(hashy+1,hashy+1+cnty,a[i].y)-hashy;
}
}
int lowbit(int x)
{
return x&(-x);
}
void update(int pos)
{
while(pos n)
{
tree[pos] = dp[pos];
for(int i=1;i1)
tree[pos] = max(tree[pos],tree[pos-i]);
pos += lowbit(pos);
}
}
int query(int l, int r)
{
int ans = 0;
while(r>=l)
{
ans = max(ans,dp[r]);
if(l==r) break;
for(--r;r-l>=lowbit(r);r-=lowbit(r))
ans = max(ans,tree[r]);
}
return ans;
}
int main( )
{
int t;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for(int i=1 ; i)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
}
sort(a+1,a+1+n,cmp);
init( );
memset(dp,0,sizeof(dp));
memset(tree,0,sizeof(tree));
for(int i=1 ; i)
{
dp[a[i].y]=max(dp[a[i].y],query(1,a[i].y-1)+a[i].w);
update(a[i].y);
}
int ans = 0;
for(int i=1;ii)
ans = max(ans,dp[i]);
printf("%d\n",ans);
}
return 0;
}
View Code
HDU 6447 YJJ’s Salesman （树状数组 + DP + 离散）
标签：str one play turn pen bre 一个 alt bool
原文地址：https://www.cnblogs.com/shuaihui520/p/9536982.html
评论