题目描述
小h看书从第 K 页开始看，准备看到第 M 页。但是小h只能够跳着看，每次最多跳 D 页，即看完第 x 页下一次可以选择 [x+1,x+D] 这个区间内任意一页看。每跳一次会花费 A 的代价，现在已知其中有 N 页，看完之后能获得一定的收益。求从第 K 页跳着看到第 M 页的最大收益。
输入：第一行五个数 K,M,D,A,N 之后 N 行每行两个数 $x_i,v_i$，表示看完第 x_i 页会获得 v_i 的收益
对于 20 % 的数据， N≤1000
对于另外 30 % 的数据， D≤100
对于 100 % 的数据， N≤10^5,0≤K,M,D,A<10^9
Sol:
对于 20 %的数据，考虑暴力DP
容易设计状态 dp[i] 表示到第i号页的最大收益，定义第 K 页为 0 号点， M 页为 N+1 号点
设计状态
dp[i]=\max\limits_{j=0}^{i-1} dp[j]+ \lceil (x_i-x_j)/D \rceil *A
时间复杂度 O(n^2)
对于 30 %的数据，考虑对上取整变形
令:
x_i=t_i*D+c _i ,
x_j=t_j*D+c _j
相减：
x_i-x_j=(t_i-t_j)*D+c _i-c_j
观察到:
当 c_i<=c_j ，上取整结果为 t_i-t_j
当 c_i>c_j ，上取整结果为 t_i-t_j+1
所以可以将DP式子变形:
dp[i]=\max\limits_{j=0}^{i-1} dp[j]+ (t_i-t_j)*A+(c_i>c_j)*A
=\max\limits_{j=0}^{i-1} dp[j]-t_j*A+ t_i*A+(c_i>c_j)*A
我们考虑维护 dp[j]-t_j*A 的最大值，由于 D<=100 可以用数组直接维护
时间复杂度 O(N*D)
对于$100$ %的数据，在将所有可能出现的余数离散化后，将数组换成线段树即可，由于余数个数不多余 n+2 个，所以空间和时间复杂均为
O(nlogn)
Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
typedef long long ll;
int k,m,d,a,n,siz;
struct P{
int x,v,t;
}p[N];
bool cmp(P a,P b){
return a.x<b.x;
}
vector<int>num;
int find(int w){
return lower_bound(num.begin(),num.end(),w)-num.begin()+1;
}
ll maxn[N*4],dp[N];
void update(int o,int l,int r,int pos,ll k){
if(l==r){
maxn[o]=max(maxn[o],k);
return ;
}
int mid=l+r>>1;
if(pos<=mid) update(o<<1,l,mid,pos,k);
else update(o<<1|1,mid+1,r,pos,k);
maxn[o]=max(maxn[o<<1],maxn[o<<1|1]);
}
ll check(int o,int l,int r,int x,int y){
if(x>y) return -LLONG_MAX/2;
if(x<=l&&r<=y){
return maxn[o];
}
ll tmp=-LLONG_MAX;
int mid=l+r>>1;
if(x<=mid) tmp=max(tmp,check(o<<1,l,mid,x,y));
if(y>mid) tmp=max(tmp,check(o<<1|1,mid+1,r,x,y));
return tmp;
}
signed main(){
cin>>k>>m>>d>>a>>n;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&p[i].x,&p[i].v);
p[i].t=p[i].x/d;
}
sort(p+1,p+1+n,cmp);
p[0].x=k;
n++;
p[n].x=m;
for(int i=0;i<=n;i++){
num.push_back(p[i].x%d);
p[i].t=p[i].x/d;
}
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
siz=num.size();
for(int i=1;i<=siz*4;i++) maxn[i]=-LLONG_MAX/2;
update(1,1,siz,find(p[0].x%d),p[0].t*a);
for(int i=1;i<=n;i++){
int u=find(p[i].x%d);
dp[i]=max(check(1,1,siz,1,u-1)-a,check(1,1,siz,u,siz))-p[i].t*a+p[i].v;
update(1,1,siz,u,dp[i]+p[i].t*a);
}
cout<<dp[n];
return 0;
}