P6647

· · 个人记录

[CCC 2019] Tourism

首先我们定义状态 f(i)，表示游览到第 i 个景点，且所用天数最少，此时的最大收益是多少。

我们当然可以直接认为这个最小天数是 \lceil \dfrac{i}{k}\rceil，然后转移，实际上还有更加简单的方法。

状态转移方程：

f(i)=\max_{i-k\le j< i}\{f(j)+\max_{p\in[j+1,i]}\{a_p\}\}

所谓简单的方法就是：

f(i)=\max_{i-k\le j< i}\{f(j)+\max_{p\in[j+1,i]}\{a_p\}\}-\infty

这样多出一天就要付出极为昂贵的代价，自然会在天数尽量少的情况下选择，最后输出答案的时候把减去的 \infty 重新加上即可。

然后就是处理 \max_{i-k\le j< i}\{f(j)+\max_{p\in[j+1,i]}\{a_p\}\}。

这里使用单调栈，保证栈内元素不升，然后我们我们在加入新元素 a_i 的过程中，显然弹出的元素对应的位置是需要修改的，再用一下线段树修改。因为对于每个栈内的元素至多修改一次，所以是 O(n\log n) 的。

总的时间复杂度亦是 O(n\log n) 的。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e6,inf=1e12;

ll n,k,top;

ll a[N+5],st[N+5],f[N+5];

struct sgt{
    ll l,r,ma,laz;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define ma(x) tree[x].ma
    #define laz(x) tree[x].laz
}tree[N*4+5];

void build(ll p,ll l,ll r) {
    l(p)=l;r(p)=r;
    if(l==r) return;
    ll mid=(l+r)>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
}

void spread(ll p) {
    laz(p<<1)+=laz(p);laz(p<<1|1)+=laz(p);
    ma(p<<1)+=laz(p);ma(p<<1|1)+=laz(p);
    laz(p)=0;
}

void modify(ll p,ll l,ll r,ll k) {
    if(l<=l(p)&&r>=r(p)) {laz(p)+=k;ma(p)+=k;return;}
    ll mid=(l(p)+r(p))>>1;
    spread(p);
    if(l<=mid) modify(p<<1,l,r,k);
    if(r>mid) modify(p<<1|1,l,r,k);
    ma(p)=max(ma(p<<1),ma(p<<1|1));
}

ll getmax(ll p,ll l,ll r) {
    if(l<=l(p)&&r>=r(p)) return ma(p);
    ll mid=(l(p)+r(p))>>1;
    spread(p);
    if(r<=mid) return getmax(p<<1,l,r);
    if(l>mid) return getmax(p<<1|1,l,r);
    return max(getmax(p<<1,l,r),getmax(p<<1|1,l,r));
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();k=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read();
    }

    build(1,0,n);

    for(ll i=1;i<=n;i++) {
        while(top>0&&a[i]>=a[st[top]]) {
            modify(1,st[top-1],st[top]-1,a[i]-a[st[top]]);top--;
        }
        st[++top]=i;modify(1,i-1,i-1,f[i-1]+a[i]);
        f[i]=getmax(1,max(0ll,i-k),i-1)-inf;
    }

    write(f[n]+(n+k-1)/k*inf);

    return 0;
}