2016 UESTC Training for Dynamic Programming L – 柱爷抢银行MkⅣ dp 线段树优化

Source

2016 UESTC Training for Dynamic Programming

My Solution

dp 线段树优化

dp[i] = max(dp[j]) + v[i] //

x[i] – y[i] <= x[j] < x[i]

首先按x[i]升序排序

用线段树优化时间，单点更新，区间查询

x[i],y[i]<=1e9,

需要离散化

max(dp[j]) = dpj = Query(l, r);

算出以后更新进去Modify(x, dp[i]);， 这样一次插入进去

当考虑dp[i]的时候里面必然是1 - i-1 是插入的，

因此满足只能从较小号数的银行才能到达较大号数的银行

复杂度 O(NLogN)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 100000 + 8;
int xa[maxn], xb[maxn], nn, v[maxn], y[maxn];
//LL dp[maxn];

LL Top[4*maxn], Cover[4*maxn], dp[maxn];
int sz;   //size

LL _Query(int a, int b, int l, int r, int Ind)
{
    if(a <= l && b >= r) return Top[Ind];
    int mid = (l + r)>>1;
    LL ret = Cover[Ind];
    if(a <= mid) ret = max(ret, _Query(a, b, l, mid, Ind<<1)); if(b > mid) ret = max(ret, _Query(a, b, mid+1, r, (Ind<<1)+1)); return ret; } void _Modify(int a, int l, int r, int Ind, LL d) { if(l == r && l == a){ Cover[Ind] = Top[Ind] = d; return; } int mid = (l + r)>>1;
    if(a <= mid) _Modify(a, l, mid, Ind<<1, d);
    else _Modify(a, mid+1, r, (Ind<<1)+1, d);
    Top[Ind] = max(Top[Ind<<1], Top[(Ind<<1)+1]); } inline LL Query(int a, int b) {return _Query(a, b, 1, sz, 1);} inline void Modify(int a, LL d) {return _Modify(a, 1, sz, 1, d);} //!WA2 这里Modify 的 d 没有改成 long long …… int main() { #ifdef LOCAL freopen("a.txt", "r", stdin); #endif // LOCAL int n, x, l, r; long long dpj; //dp[maxn] ==>> dp
    scanf("%d", &n);sz = n;
    for(int i = 0; i < n; i++){
        scanf("%d%d%d", &xa[i], &v[i], &y[i]);
    }

    memcpy(xb, xa, sizeof xa);
    sort(xa, xa + n);
    nn = unique(xa, xa + n) - xa;

    memset(Top, 0, sizeof Top);
    memset(Cover, 0, sizeof Cover);
    for(int i = 0; i < n; i++){                                            //!这里坐标统一为 1 ~ nn 了
        x = lower_bound(xa, xa + nn, xb[i]) - xa + 1;
        l = lower_bound(xa, xa + nn, xb[i] - y[i]) - xa + 1;
        r = x;

        dpj = Query(l, r);
        dp[i] = dpj + v[i];                                                 //!如果x本来有值也不要紧，被加在dpi里了
        Modify(x, dp[i]);
    }
    //!WA2, 因为dpi可能是分开的所以， ans = max(dp[i]);这个不是test2 的是另外的地方的把
    LL ans = 0;                                                             //cout<<dp[0]<<endl;
    for(int i = 0; i < n; i++) ans = max(ans, dp[i]);
    printf("%lld", ans); //ans 不是 dp[n-1] ☺☺
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx