题意
给定长度为 $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协议，复制请保留原文出处。