【Foreign】阅读 [线段树][DP]

阅读

Time Limit: 10 Sec Memory Limit: 256 MB

Description

Input

Output

Sample Input

　　0 10 4 10 2
　　3 10
　　8 5

Sample Output

　　-20

HINT

Main idea

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

Solution

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

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

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

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

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

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

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<ctime>

 #include<cmath>

 using namespace std;  

 typedef long long s64;

 const int ONE=;

 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=,Q=;char c;

         while( (c=getchar())< || c> )

         if(c=='-')Q=-;

         res=c-;

         while( (c=getchar())>= && c<= )

         res=res*+c-;

         return res*Q;

 }

 void Build(int i,int l,int r)

 {

         Node[i].maxx = -INF;

         if(l==r) return;

         int mid=(l+r)>>;

         Build(i<<,l,mid);    Build(i<<|,mid+,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)>>;

         if(L<=mid) Update(i<<,l,mid,L,x);

         else Update(i<<|,mid+,r,L,x);

         Node[i].maxx = max(Node[i<<].maxx , Node[i<<|].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)>>;

         if(L<=mid) Query(i<<,l,mid,L,R);

         if(mid+<=R) Query(i<<|,mid+,r,L,R);

 }

 int main()

 {

         K=get();    M=get();    D=get();    A=get();

         n=get();

         for(int i=;i<=n;i++)

             pos[i]=get(),    val[i]=get();

         pos[]=K;    pos[++n]=M;

         for(int i=;i<=n;i++)  li[++Num]=pos[i] % D;

         sort(li+,li+Num+);    Num=unique(li+,li+Num+) - li -;

         Build(,,Num);

         Mod = lower_bound(li+,li+Num+, K%D) - li;

         Update(,,Num,Mod,);

         for(int i=;i<=n;i++)

         {

             F = -INF;

             Mod = lower_bound(li+,li+Num+, pos[i]%D) - li;

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

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

             Update(,,Num, Mod,F);

         }

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

 }

巴特西