[FJWC2019 Day1] 全连

时间限制：1000MS      内存限制：262144KB

难度： \(4.5\)

• 题目描述

给定两个长度为 \(n\) 的序列 \(a\) 和 \(t\)，可以在其中选择一些元素构成集合 \(S\) ，使得 \(\sum\limits_{i \in S}{a_i \times t_i}\) 最大。

同时，集合 \(S\) 还要满足 \(\forall i \in S, \forall j \in (i-t_i, i+t_i)\) ， \(j \notin S\) 。

• 输入格式

第一行一个整数 \(n\) ；

第二行 \(n\) 个整数表示序列 \(t\) ；

第三行 \(n\) 个整数表示序列 \(a\) 。

• 输出格式

一行一个整数，即答案。

• 样例输入

• 样例输出

• 样例说明

\(S=\{1,3,5\}\)，答案 \(=2 \times 3 + 2 \times 2 + 2 \times 4 = 18\) 。

• 数据规模与约定

保证 \(t_i \leq n\) ， \(a_i \leq 10^9\) ，\(1 \leq n \leq 10^6\) 。

 

 

YZOJ P4257, YZOJ P3993

---

 

 

 

其实是大水题，但是我这么简单的DP方程都没想清楚直接快乐爆零。

可以发现，只要 \(S\) 中相邻最近的两个元素满足条件就可以了。所以设 \(f_i\) 为 前 \(i\) 个中元素中，选择第 \(i\) 个元素的最大答案。

所以显然 \(f_i = \max \limits _ {j + t_j \le i \land j \le i – t_i}{f_j + t_i \times a_i}\) ，答案就是 \(\max\limits_i{f_i}\) 。

然后这是一个裸的二维偏序，即贡献有两个条件 \(j+t_j \leq i\) 和 \(j \leq i-t_i\) 。最常见做法的是把一维拿去排序，剩下一维拿数据结构维护。在这里，把 \(j+t_j\) 拿去排序，然后维护 \(i-t_i\) 的树状数组，时间复杂度就是 \(O(nlogn)\) 。

（因为我比较菜，一直在纠结贡献的顺序即 \(i>j\) ，所以在这里说明一下：首先 \(j+t_j\) 排完序后就是单调的，对于当前元素 \(i\) 就可以快速找出哪些元素是可以可以对其产生贡献的。又 \(i\) 也是单调的，始终满足 \(j+t_j \leq i\) ，所以这个元素都可能对 \(i\) 后的元素产生贡献，就把它加入树状数组。那么对于当前元素 \(i\) ，要对它产生贡献只剩下 \(j \leq i-t_i\) 这一个条件了。因为树状数组维护区间 \([1, o]\) 的特性，所以加入树状数组的时候把节点编号和其对应 \(f\) 加进去，查询 \(i-t_i\) 即可。特别注意，这里的贡献仍然是顺序的！不要像我一样犯傻，因为随着 \(i\) 的增加才会有更多的 \(j+t_j \leq i\) 满足！