[FJWC2019 Day1] 全连

[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\) 满足!

 

 

 

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注