阅读

· · 个人记录

fateice 喜欢阅读，现在他准备读一本书，他会从第K 页开始看，然后看到 第M 页。

书中的内容不一定都让fateice 有所收获，因为fateice 太强。更具体地，书中有N 页能让fateice 有所收获，阅读第T_i 页可以获得B_i 的收获值。

由于书的页数太多，fateice 会选择跳着看，但是他一次最多跳D 页（两页 页码差不大于D），然后阅读跳到的那一页内容，每次翻页他将会丧失A 的收获 值。

fateice 想在阅读这本书前就知道他能获得的最大收获值之和。

输入

第一行五个非负整数K,M,D,A,N。

接下来N行每行两个正整数T_i ,B_i 。

1\le N\le 10^5\ , 0\le B_i,A,D\le 10^9\ , 0\le K \le M \le 10^9

易得转移公式

f[i]=max(f[j]-\left\lceil\dfrac{T_i-T_j}{D}\right\rceil*A+B_i)

但O(N^2)不优

首先 我们对上取整是不好处理的

但想到 设

T_i=x_i*D+r_i T_j=x_j*D+r_j

那么\left\lceil\dfrac{T_i-T_j}{D}\right\rceil=x_i-x_j+(r_i>r_j)

对于这个我们更好处理

原式变为

f[i]=max(f[j]+x_j*A-x_i*A+(r_i>r_j)*A+B_i)

因此我们想到 维护f[j]+x_j*A的最大值

其次 突破点在于 我们要想到

若有两个点到当前点的距离模D 同余，则我们只需考虑后一个点。

这里的余数是-k后的

这是因为一次一次跳D，那必将经过后面那个点

而不加上后面的那个点的权值，显然是不优的

所以我们可以按T_i\ mod\ D的值分类

离散化之后很明显 最多就N个

那么后面就很常规了

线段树维护f[j]+x_j*A最大值

对于\le r_i的部分我们找最大值=X

对于r_i<的部分我们找最大值+A=Y

然后取两边更大的一个转移

最后再把新的得到的一个替代掉原来和自己余数相同的一个

总结：这道题告诉我们这种上取整的处理方式 和 这种同余优化的思想