十分显然的DP
二分金币数量
然后对二分的金币数量跑DP求最大获利
方程：
设 f [ i ] 表示在第 i 个格子里的最大获利
f [ i ] = max( f [ j ] ) + val [ i ] （pos[ j ]+max(1,m-g) ≤ pos[ i ] && pos[ j ]+m+g ≥ pos[ i ]）
因为数据较大，我们要考虑优化
可以发现，转移只有在一段固定长度的区间中，而我们要的是这段区间的最大值
所以十分显然的单调队列优化 DP
然后就是一堆细节了
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=5e5+7; int n,m,t; int pos[N],val[N]; ll f[N];//要开long long int fir,las,q[N]; int L;//L是当前还未入队过的点的闭区间左端点 inline bool check(int p)//判断用p金币能否符合要求 { bool flag=0; int l=max(1,m-p),r=m+p; memset(f,128,sizeof(f)); f[0]=0; memset(q,0,sizeof(q)); fir=0; las=0; L=1;//初始化 for(int i=1;i<=n;i++) { while((pos[q[fir]]+r<pos[i])&&fir<=las) fir++;//把不符合条件的点踢出单调队列 if(fir<=las&&pos[q[fir]]+l<=pos[i]) f[i]=f[q[fir]]+val[i];//注意判断合法性 //后一个判断是因为初始q[fir]为0，0+m-g可能大于pos[i]，除了0队列保证pos[q[j]]+m-g<=pos[i] if(f[i]>=t) { flag=1; break; }//可以在任意位置结束 while(L<=i&&pos[L]+l<=pos[i+1])//把可以加入的点加入，另一个条件下一轮循环时会判断 //现在不能判，要保证所有点都进过队列 { while(f[q[las]]<=f[L]&&fir<=las) las--;//基本操作 q[++las]=L; L++;//加入队列 } } return flag; } int main() { n=read(); m=read(); t=read(); for(int i=1;i<=n;i++) pos[i]=read(),val[i]=read(); int l=0,r=1e9,mid; while(l<=r)//二分 { mid=l+r>>1; if(check(mid)) r=mid-1;//判断 else l=mid+1; } printf("%d",l>1e9 ? -1 : l); return 0; }