阅读

Time Limit: 10 Sec Memory Limit: 256 MB

Description

A君喜欢阅读，现在他准备读一本书，他会从第K页开始看，然后看到第M页。
书中的内容并不一定都让A君愉悦，或者说，A君更喜欢看书中的精华。更具体地，书中有N页能让A君感到愉悦，阅读第T页可以获得B;的愉悦度。
由于书的页数实在太多，因此A君会选择跳着看，但是他一次最多跳D页(两页页码差不大于D)，然后阅读跳到的那一页的内容，每次翻页他将会丧失A的愉悦度。
现在A君想知道他阅读完这本书，能得到的愉悦度之和最大能是多少。

Input

img

Output

img

Sample Input

0 10 4 10 2
　　3 10
　　8 5

Sample Output

-20

HINT

img

Main idea

从K走向M，路上有n个收益点，表示到了pos位置可以增加val的收益，每次最多可以走D步，走一次损耗A。求最大收益。

Solution

这题必然是一道DP，我们层层深入来思考。

先从20%考虑：首先我们一下子就想到了暴力DP，令f[i]表示到了第i个收益点的最大收益，显然对于每个收益点我们可以O(n)往前枚举每种情况，两个收益点间到达的方法必然是每次都跳D步，最后补上一段，那么步数就是img，这样做就是O(n^2)的算法。

再考虑另外30%：我们发现，我们可以将pos%D同余的放在一个集合，因为这样的话两点之间到达必然是一直跳D步的，那么显然在同一个集合里的点最后一个点对后面的点贡献更优。由于这时候D<=100，我们先预处理，然后新增点的时候枚举D更新即可。

考虑100%的做法：我们将前面两种方法结合起来，我们发现img，由于中间这个步数是一个上取整的东西，不好维护，于是我们可以把它拆成img，这个东西具体是+0还是+1我们可以举例子来思考。发现根据余数有关：当pos[j]%D<pos[i]%D的时候+1，否则+0。然后我们就可以用一个线段树来优化这个DP。对于叶子节点 i 维护 pos%D=i 的最值，这里的最值指的是上述式子中仅仅与 j 有关的一项，因为后面的val[i]以及其它项是都要加的，所以可以不管。然后我们再往线段树里面每次加入f[i]，这样显然就是区间查询最值、单点修改的一个线段树结构。效率O(nlogn)

这里还有一个技巧就是：img所以我们维护线段树权值的时候可以不用管pos，最后对于答案加减操作即可。

这样我们就解决了这道题(≧▽≦)/。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;

typedef long long s64;
const int ONE=1000005;
const s64 INF=1e18;

int K,M,D,A,n;
s64 F,res;
int pos[ONE],val[ONE];
int Mod;
int li[ONE],Num;

struct power
{
    s64 maxx;
}Node[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Build(int i,int l,int r)
{
    Node[i].maxx = -INF;
    if(l==r) return;
    int mid=(l+r)>>1;
    Build(i<<1,l,mid);    Build(i<<1|1,mid+1,r);
}

void Update(int i,int l,int r,int L,s64 x)
{
    if(l==r)
    {
        Node[i].maxx = max(Node[i].maxx,x);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid) Update(i<<1,l,mid,L,x);
    else Update(i<<1|1,mid+1,r,L,x);
    Node[i].maxx = max(Node[i<<1].maxx , Node[i<<1|1].maxx);
}

void Query(int i,int l,int r,int L,int R)
{
    if(L > R) return;
    if(L<=l && r<=R)
    {
        res=max(res,Node[i].maxx);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid) Query(i<<1,l,mid,L,R);
    if(mid+1<=R) Query(i<<1|1,mid+1,r,L,R);
}

int main()
{
    K=get();    M=get();    D=get();    A=get();

    n=get();
    for(int i=1;i<=n;i++)
        pos[i]=get(),    val[i]=get();
    pos[0]=K;    pos[++n]=M;

    for(int i=0;i<=n;i++)  li[++Num]=pos[i] % D;
    sort(li+1,li+Num+1);    Num=unique(li+1,li+Num+1) - li -1;

    Build(1,1,Num);
    Mod = lower_bound(li+1,li+Num+1, K%D) - li;
    Update(1,1,Num,Mod,0);
    for(int i=1;i<=n;i++)
    {
        F = -INF;
        Mod = lower_bound(li+1,li+Num+1, pos[i]%D) - li;

        res=-INF;    Query(1,1,Num,1,Mod-1);    F=max(F, res - A + val[i] );
        res=-INF;    Query(1,1,Num,Mod,Num);    F=max(F, res + val[i]);

        Update(1,1,Num, Mod,F);
    }

    printf("%I64d",F + (s64)A*(K/D) - (s64)A*(M/D));
}