CF1484E. Skyline Photo

题目链接:https://codeforces.com/contest/1484/problem/E

题目大意

n 栋楼房,每栋楼有一个高度 a_i 和美丽值 b_i
现在,你需要把这 n 栋楼房划分成若干个连续段,每一个连续段的美丽值为该段中最矮的楼房的美丽值。总的划分美丽值为每个连续段的美丽值之和。

你需要求出最大可能的总划分美丽值。

Solution

考虑 n^2 的 DP,有
dp_i=max{dp_j+clac(j+1,i) } \quad \quad 1\leq j \leq i-1
考虑一下优化,我们想到当 i \to i+1 转移时,i+1 可以从 i+1 覆盖到从右往左第一个小于 h_{i+1} 的右边的位置(可以用单调栈处理出这个位置)。

可以用线段树维护出单点更新 dp_x 的值,然后区间更新 [j+1,i] 中计算出的 clac(j+1,i) 的值。

于是这个 n^2 的式子就可以通过线段树的一次询问来得到最大值了。复杂度 nlog(n)

其实这道题也有线性的做法

我们将式子变形,维护一个单调栈,有
dp_i=max_{k=1}^{top} {(max_{j=s_{k-1}+1}^{s_k}dp_j) +b[k] }
然后考虑维护一个 max_{j=s_{k-1}+1}^{s_k}dp_j 就好了 。

#include<bits/stdc++.h>
#define ll long long  
const int N = 3e5+10;
int h[N],b[N],n;
int s[N],t;
ll val[N],mxf[N],f[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&h[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&b[i]);
    val[0] = - 0x7f7f7f7f7f7f7f7f;
    for(int i=1;i<=n;++i){
        ll Mxf = f[i-1] ;
        while(t&&h[s[t]]>h[i]){
            Mxf = std::max(Mxf,mxf[t]);
            t--;
        }
        s[++t] = i;
        mxf[t] = Mxf;
        val[t] = Mxf + b[i];
        val[t] = std::max(val[t-1],val[t]);
        f[i] = val[t];
    }
    printf("%lld",f[n]);
    return 0;
} 
分类: 单调系列

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注