题意：
给定长度为$5e5$的带权含坐标的点序列，从$0$位置向右每次隔$(d-g,d+g)$取点权（$d$给定），权值和不少于$k$，求最小的$g$。
程序1（50pt）：
对$g$在$[0,max{x_{i}-d}]$上二分。判定：定义$f_{i}$为取前$i$点的最大和，且
$ f_{i}+s_{j} o f_{j} ( j>i,x_{j}in [x_{i}+(d-g),x_{i}+(d+g)] ) $
交上去发现$T$了，一看，二分域太大。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; const LL inf=1LL<<34; const int N=500000; int n,d,x[N+3]; LL k,s[N+3],f[N+3]; bool chk(int g){ for(int i=1;i<=n;i++) f[i]=-inf; f[0]=0; for(int i=0;i<=n;i++) if(f[i]!=-inf){ int j; for(j=i+1;x[j]<x[i]+(d-g)&&j<=n &&x[j]<=x[i]+(d+g);j++); for(;x[j]<=x[i]+(d+g)&&j<=n;j++) f[j]=max(f[j],f[i]+s[j]); } LL tmp=-inf; for(int i=1;i<=n;i++) tmp=max(tmp,f[i]); return tmp>=k; } int main(){ scanf("%d%d%lld",&n,&d,&k); for(int i=1;i<=n;i++) scanf("%d%lld",&x[i],&s[i]); x[0]=0; int l=0,r=x[n]-d,mid,ans=-1; while(l<=r){ mid=(l+r)>>1; if(chk(mid)){ ans=mid; r=mid-1; } else l=mid+1; } printf("%d",ans); return 0; }
程序2（90pt）：
考虑以保证对于每两点间距离能跳过去作为二分边界，交上去证明我错了。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; const LL inf=1LL<<62; const int N=500000; int n,d,x[N+3]; LL k,s[N+3],f[N+3]; bool chk(int g){ for(int i=1;i<=n;i++) f[i]=-inf; f[0]=0; for(int i=0;i<=n;i++) if(f[i]!=-inf){ int j; for(j=i+1;x[j]<x[i]+(d-g)&&j<=n &&x[j]<=x[i]+(d+g);j++); for(;x[j]<=x[i]+(d+g)&&j<=n;j++) f[j]=max(f[j],f[i]+s[j]); } LL tmp=-inf; for(int i=1;i<=n;i++) tmp=max(tmp,f[i]); return tmp>=k; } int main(){ scanf("%d%d%lld",&n,&d,&k); for(int i=1;i<=n;i++) scanf("%d%lld",&x[i],&s[i]); int maxd=x[1]; for(int i=2;i<=n;i++) maxd=max(maxd,x[i]-x[i-1]); x[0]=0; int l=0,r=maxd,mid,ans=-1; while(l<=r){ mid=(l+r)>>1; if(chk(mid)){ ans=mid; r=mid-1; } else l=mid+1; } printf("%d",ans); return 0; }
程序3（100pt）：
思考一下，发现权值和不能达到$k$的等价条件是正权和小于$k$，于是可以在二分之前排除掉不合法的情况。
思考一下，发现负权点对于确定$g$的最大值是没有贡献的，于是考虑以保证能跳过每两个正权点间距离作为二分边界，再重构一下DP代码，交上去过了。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; const LL inf=1LL<<62; const int N=500000; int n,d,x[N+3]; LL k,s[N+3],f[N+3]; bool chk(int g){ for(int i=1;i<=n;i++) f[i]=-inf; f[0]=0; for(int i=0;i<=n;i++) if(f[i]!=-inf){ for(int j=i+1;j<=n;j++){ if(x[j]<x[i]+(d-g)) continue; if(x[j]>x[i]+(d+g)) break; f[j]=max(f[j],f[i]+s[j]); if(f[j]>=k) return true; } } return false; } int main(){ scanf("%d%d%lld",&n,&d,&k); for(int i=1;i<=n;i++) scanf("%d%lld",&x[i],&s[i]); int pre=0,maxd=0; LL sum=0; x[0]=0; for(int i=1;i<=n;i++) if(s[i]>0){ sum+=s[i]; maxd=max(maxd,x[i]-x[pre]); pre=i; } if(sum<k){ printf("-1"); return 0; } int l=0,r=maxd,mid,ans=-1; while(l<=r){ mid=(l+r)>>1; if(chk(mid)){ ans=mid; r=mid-1; } else l=mid+1; } printf("%d",ans); return 0; }
小结：
DP是最简单的DP，二分也没有什么骚操作，就是边界这种东西……
好像摸到一点意思：求最大和的时候，负权对于答案的最低要求没有贡献，所以二分上界是要确保能取到所有正权。
也就是说，“最优答案”和“合法答案/最低要求/搜索边界”需要的数据不太一样，经常会用贪心思路找边界。
（错了再改）