AtCoder Educational DP Contest Q - Flowers 题解

题意

有一排花，共 $n$ 个，第 $i$ 个的高度是 $h_i$ ，权值是 $a_i$ ，保证高度互不相同。现在拿走一些花，使剩下的花高度单调递增，问剩下的花权值之和最大是多少。

数据范围与约定：

$1 \leq n \leq 2 \times10^5，1\leq h_i \leq n，1\leq a_i\leq 10^9，h_1,h_2,···,h_N$ 的值均不相等。

前置知识

前置知识：线段树、动态规划

思路

看到这题我们能想到一个很显然的dp做法：设 $f[i]$ 为取前 $i$ 朵花中的一些花，且第 $i$ 朵最高时能取得的最大权值，则 $f[i]=max\{f[j],j<i,h[j]<h[i]\}+a[i]$ ，在每次取到 $i$ 时再遍历一次 $f[1]$ 至 $f[i-1]$ 即可。可是这样做的复杂度在是 $O(n^2)$ ，每次取一个 $i$ 都需要从头遍历一次，显然在这题的数据范围下会tle。
于是我们考虑如何优化取得 $f[j]_{max}(j<i)$ 的过程。对于求区间最值问题，往往用线段树对区间最值进行维护是一个十分方便的途径：
在这道题目中，对于第 $i$ 朵花，更新答案 $f[i]$ 时查询高度在区间 $[1,h[i]-1]$ 内 $f$ 数组的最大值，更新完 $f[i]$ 之后再将 $f[i]$ 插入到线段树中，每次查询和插入的时间复杂度是 $O(logn)$ ，需要进行 $n$ 次操作。
于是我们可以在 $O(nlogn)$ 的时间内解决本题。
需要注意的细节是，在求解完 $f$ 数组的全部值之后， $f[n]$ 并不一定是要求的答案，因为第 $n$ 朵花可能并不够高，所以我们还需要遍历一遍 $f$ 数组找出最大值，才能求出答案。

代码实现

//略去了上面的头文件和快读快写函数，以及using ll = long long;
int n;
struct flower{
    ll h;
    ll a;
} fl[200005];
ll tree[800005],ans[200005];
inline void pushup(int p){tree[p] = max(tree[p<<1],tree[(p<<1)+1]);}
void modify(int d,int l,int r,int p,ll val){    //修改高度h在[1,d]区间内，ans的最大值
    if(l==r && r==d){tree[p] = max(tree[p],val);}
    else{
        int mid = (l+r)>>1;
        if(mid>=d){modify(d,l,mid,p<<1,val);}
        else{modify(d,mid+1,r,(p<<1)+1,val);}
        pushup(p);
    }
}
ll query(int l,int r,int nl,int nr,int p){    //查询高度在[l,r]区间内，ans的最大值
    if(nl>r || nr<l)    return 0;
    else{
        if(nl>=l && nr<=r)  return tree[p];
        else{
            int mid = (nl+nr)>>1;
            return max(query(l,r,nl,mid,p<<1),query(l,r,mid+1,nr,(p<<1)+1));
        }
    }
}
void solve(){
    memset(tree,0,sizeof(tree));
    // freopen("at_dp_q.in","r",stdin); 
    read(n);
    for(int i=1;i<=n;i++)   read(fl[i].h);
    for(int i=1;i<=n;i++)   read(fl[i].a);
    for(int i=1;i<=n;i++){
        ans[i] = query(1,fl[i].h-1,1,n,1)+fl[i].a;    //转移
        modify(fl[i].h,1,n,1,ans[i]);
    }
    ll maxans = 0;
    for(int i=1;i<=n;i++)   maxans = max(maxans,ans[i]);
    write(maxans);
}
int main(){
    solve();
    return 0;
}