[ABC218H] Red and Blue Lamps 题解

· · 题解

离 2023 NOI 春季测试 还有 4 天，随机拷打 ABC 锻炼手感。

感觉一下 O(nk) 的 dp，f_{0/1,i,j} 表示选或不选第 i 个灯，前 i 个灯，有 j 个是红色时的最大价值。

寄了，无法上数据结构优化转移，所以它必须带点性质，

恰好选 R 个，给我一种 wqs 二分的感觉，函数 g(x) 表示选 x 个红色点的最大价值，g(x)-g(x-1) \le g(x+1)-g(x)，在 x \le \lfloor \frac{n}{2} \rfloor 时成立，大于的时候反过来，人话说就是这个函数是上凸的。

套路抛弃选 R 个的限制，变成任意选的时候最大价值，二分斜率切这个凸包，转移的时候额外加上权值，最后减去 R \times \text{mid}，内层是个很典的 O(n) dp，做完了。

我看官方题解给的是写成区间 dp 的形式，通过凸性做分治，也挺好的。

Code.

#include<bits/stdc++.h>
#define ll long long
int read()
{
    int x=0; bool f=0; char ch=getchar();
    while(ch < '0' || ch > '9') f|=(ch == '-'),ch=getchar();
    while(ch >= '0' && ch <= '9') x=x*10+(ch^48),ch=getchar();
    return f ? -x : x;
}
using namespace std;
const int N=2e5+10;
int a[N],n,k,cnt[2][N]; ll f[2][N];
bool check(ll mid)
{
    f[1][1]=mid; cnt[1][1]=1;
    for(int i=2;i<=n;i++)
    {
        (f[0][i-1] < f[1][i-1] + a[i]) ? (f[0][i]=f[1][i-1]+a[i],cnt[0][i]=cnt[1][i-1]) : (f[0][i]=f[0][i-1],cnt[0][i]=cnt[0][i-1]);
        (f[0][i-1] + a[i] < f[1][i-1]) ? (f[1][i]=mid+f[1][i-1],cnt[1][i]=cnt[1][i-1]+1) : (f[1][i]=mid+f[0][i-1]+a[i],cnt[1][i]=cnt[0][i-1]+1);
    }
    return (f[1][n] > f[0][n]) ? (cnt[1][n] <= k) : (cnt[0][n] <= k);
}
int main()
{
    n=read(); k=read(); for(int i=2;i<=n;i++) a[i]=read();
    ll l=-2e9,r=2e9,res=0;
    while(l <= r)
    {
        ll mid = (l + r) >> 1ll;
        if(check(mid)) l=mid+1,res=max(f[1][n],f[0][n])-k*mid;
        else r=mid-1;
    }
    printf("%lld\n",res);
    return 0;
}