树状数组+DP

发表于2021-10-24更新于2021-10-24阅读次数

YJJ’s Salesman

题意：A从(0,0)走到(1e9,1e9)，规定只能向下走，向右走，向右下走。在二维平面上有n < 1e5个村庄，
每个村庄有一个奖励值，规定只有从左上方向来到达村庄方可获得奖励值，问最多可以获得多少奖励值。












很显然有DP[ i ][ j ]=DP[i-1][j]+DP[i][j-1]+DP[i-1][j-1];
但是这需要DP[1e5][1e5]才可以操作，显然不行。
于是我们考虑只遍历每个点。

踩坑：DP更新的时候，只能从右往左更新，因为它是要求从左上方下来才可以，这样子就不包含从左来的点。如果从左往右更新，那么就包含了从左来的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
* @Author: Marhoosh
* @Date:   2021-07-22 10:27:29
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-24 21:17:24
*/
//优化遍历问题
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e5+11;
struct Point{
    ll x,y,w;
    bool operator < (const Point &b) const {
        if(y==b.y)  return x>b.x;//需要从右向左更新
        return y<b.y;
    }
}p[maxn];
ll f[maxn],x[maxn];
ll n;

ll lowbit(ll x){return x & -x;}

void update(ll x,ll val){
    for(;x<=n;f[x]=max(val,f[x]),x+=lowbit(x));
}

ll query(ll x){
    ll ans=0;
    for(;x>=1;ans=max(ans,f[x]),x-=lowbit(x));
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll ca;cin>>ca;
    while(ca--){
        memset(f,0,sizeof(f));
        cin>>n;
        for(ll i=1;i<=n;i++){
            ll y,w;cin>>x[i]>>y>>w;
            p[i]={x[i],y,w};
        }
        sort(p+1,p+n+1);
        sort(x+1,x+n+1);
        ll l=unique(x+1,x+n+1)-(x+1);
        for(ll i=1;i<=n;i++){
            p[i].x=lower_bound(x+1,x+l+1,p[i].x)-x;
        }    
        for(ll i=1;i<=n;i++){
            ll uu=query(p[i].x-1)+p[i].w;
            update(p[i].x,uu);
        }
        cout<<query(l)<<endl;    
    }
    return 0;
}