欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

J - YJJ‘s Salesman-----------------------思维(树状数组+dp)

程序员文章站 2022-06-09 17:42:15
...

J - YJJ‘s Salesman-----------------------思维(树状数组+dp)
J - YJJ‘s Salesman-----------------------思维(树状数组+dp)
题意:
给定n个坐标,每个坐标都有一个属性值。问你从(0,0)走到(1e9,1e9)属性之和的最大值
你可以向右,向下,向右下走。只有向右下走才能获得属性值?
问最大是多少?

解析:
这道题以看就是个dp。
如果是个二维dp 那么状态方程f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1]+v[i][j])
但是这样是不可取的。所以我们就不枚举行了。
我们按照x轴排序,y列从大到小遍历
然后用树状数组维护[y-1,0]的最大值即可 然后dp下去

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1000;
typedef long long ll;
ll val;
int c[N],b[N],t,n;
struct node
{
    int x,y,val;
    bool operator<(const node &W){
        if(x==W.x) return y>W.y;
        return x<W.x;
    }
}a[N];
int lowbit(int x)
{
    return x&(-x);
}
void add(int i,int val)
{
    while(i<N)
    {
        c[i]=max(c[i],val);
        i+=lowbit(i);
    }
}
int sum(int i)
{
    int mx=0;
    while(i)
    {
        mx=max(mx,c[i]);
        i-=lowbit(i);
    }
    return mx;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(c,0,sizeof c);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].val);
            b[i]=a[i].y;
        }
        sort(b+1,b+1+n);
        int m=unique(b+1,b+1+n)-b-1;
        for(int i=1;i<=n;i++) a[i].y=lower_bound(b+1,b+1+m,a[i].y)-b;
        sort(a+1,a+1+n);
        ll val=0;
        for(int i=1;i<=n;i++)
        {
             val=sum(a[i].y-1)+a[i].val;
            add(a[i].y,val);
        }
        printf("%lld\n",sum(N-1));

    }

}


相关标签: DP 树状数组