返回

P7482 不条理狂诗曲

题意

给定长度为 $n$ 的非负整数序列 $a$,定义 $f(l,r)$ 表示从 $a$ 序列的区间 $[l,r]$ 选择若干不相邻的数的和的最大值。

求 $[\sum^n_{l=1}\limits\sum^n_{r=l}\limits f(l,r)]\mod (10^9+7)$。

思路

考虑对于单个区间 $[l,r]$ 如何求 $f(l,r)$,然后发现这是一道很经典的 dp,转移方程为 $dp_i=\max(dp_{i-1},dp_{i-2}+a_i)$,可以得到枚举左端点的 $O(n^2)$ 暴力做法。

题目要求所有子区间的 $f(l,r)$ 之和,这启示我们使用分治,将问题转化为求所有满足 $l\in[L,mid],r\in[mid+1,R]$ 的 $f(l,r)$ 之和。

由于分治,满足条件的所有的子区间 $[l,r]$ 都可以表示为 $[l,mid]\cup[mid+1,r]$,即 $[L,mid]$ 的一段后缀并上 $[mid+1,R]$ 的一段前缀,因此我们只需要 $O(n)$ 地分别从 $mid$ 向左和从 $mid+1$ 向右做 $dp$,就可以合并得到满足条件的任意子区间的 $f(l’,r’)$。

注意到 $mid$ 和 $mid+1$ 这两个位置最多只能选取其中一个,进行讨论:设 $fl_i$ 表示 $mid$ 可以选也可以不选时的 $f(i,mid)$,$gl_i$ 表示强制 $mid$ 不选时的 $f(i,mid)$;设 $fr_i$ 表示 $mid+1$ 可以选也可以不选时的 $f(mid+1,i)$,$gr_i$ 表示强制 $mid+1$ 不选时的 $f(mid+1,i)$,那么就可以得到 $f(l,r)=\max(fl_l+gr_r,gl_l+fr_r)$。

考虑拆 $\max$,解 $fl_l+gr_r\lt gl_l+fr_r$,移项得 $fl_l-gl_l\lt fr_r-gr_r$,记为 ① 式。因此我们知道,对于所有满足 ① 式的 $l,r$,其对答案做的贡献为 $gl_l+fr_r$;对于所有不满足 ① 式的 $l,r$,其对答案做的贡献为 $fl_l+gr_r$。

据此,我们可以将 $[L,mid]$ 按 $fl_l-gl_l$ 排序,然后对于每一个 $r\in[mid+1,R]$,我们二分找到最大的 $i$ 满足 $fl_i-gl_i\lt fr_r-gr_r$。因此对于所有的 $l\in[L,i]$,区间 $[l,r]$ 都会对答案做 $gl_l+fr_r$ 的贡献;对于所有的 $l\in[i+1,mid]$,区间 $[l,r]$ 都会对答案做 $fl_l+gr_r$ 的贡献。

我们设 $sf_i$ 表示排序后 $fl_i$ 的前缀和,$sg_i$ 表示排序后 $gl_i$ 的前缀和,那么以 $r$ 为右端点,以 $l\in[L,mid]$ 为左端点的所有区间对答案做的贡献的总和应该就是 $(sg[i]+fr_r\times i)+(sf[mid]-sf[i]+gr_r\times(mid-i))$。

时间复杂度 $O(n\log^2n)$,需要注意 $fl,gl,fr,gr$ 不可取模,否则会影响排序,部分变量需要开 long long

代码

#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;

const int p = 1e9+7;

int n, a[N], tot;
long long ans, fl[N], fr[N], gl[N], gr[N], sf[N], sg[N];

struct Node {
    long long f, g;
    inline bool operator <(const Node &o) const {
        return f-g < o.f-o.g;
    }
} ls[N];

void solve(int l, int r) {
    if(l == r) {
        ans = (ans+a[l])%p;
        return;
    }
    int mid = (l+r)>>1;
    solve(l, mid), solve(mid+1, r);
    fl[mid]=a[mid], fl[mid+1]=gl[mid]=gl[mid+1]=0;
    for(int i=mid-1; i>=l; --i)    fl[i]=max(fl[i+1], fl[i+2]+a[i]), gl[i]=max(gl[i+1], gl[i+2]+a[i]);
    fr[mid+1]=a[mid+1], fr[mid]=gr[mid+1]=gr[mid]=0;
    for(int i=mid+2; i<=r; ++i)    fr[i]=max(fr[i-1], fr[i-2]+a[i]), gr[i]=max(gr[i-1], gr[i-2]+a[i]);
    tot = 0;
    for(int i=l; i<=mid; ++i)    ls[++tot]={fl[i], gl[i]};
    sort(ls+1, ls+1+tot);
    for(int i=1; i<=tot; ++i)    sf[i]=sf[i-1]+ls[i].f, sg[i]=sg[i-1]+ls[i].g;
    for(int i=mid+1; i<=r; ++i) {
        int j = lower_bound(ls+1, ls+1+tot, (Node){fr[i], gr[i]})-ls-1;
        ans = (ans+sg[j]%p+fr[i]%p*j%p)%p;
        ans = (ans+(sf[tot]-sf[j])%p+gr[i]%p*(tot-j)%p)%p;
    }
}

int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; ++i)    scanf("%d", &a[i]);
    solve(1, n);
    printf("%lld", ans);
    return 0;
}

附录

原题链接

参考文献

版权信息

本文原载于reincarnatey.net,遵循CC BY-NC-SA 4.0协议,复制请保留原文出处。

CC BY-NC-SA 4.0
本博客所有内容无特殊标注均为失迹原创内容,复制请保留原文出处。
Built with Hugo
Theme Stack designed by Jimmy, mod by Korita
© Licensed Under CC BY-NC-SA 4.0