特判没有石头的情况
by pomelo_nene @ 2019-05-25 14:52:40
我是不是走错了（逃）
by pomelo_nene @ 2019-05-25 14:53:09
感觉数据错了
by KokiNiwa @ 2019-06-12 22:29:34
好巧，本题AC刚好一年，无聊翻自己的帖子发现忘记填坑了。下面发一下我当时做完了之后写的题解（没发到洛谷上）。
#### 题意：
给定长度为$10^5$的带权含坐标的点序列，从$0$位置向右每次隔$(d-g,d+g)$取点权（$d$给定），权值和不少于$k$，求最小的$g$。
#### 程序1（50pt）：
对$g$在$[0,max\{x_{i}-d\}]$上二分。判定：定义$f_{i}$为取前$i$点的最大和，且
$ f_{i}+s_{j}\to f_{j} ( j>i,x_{j}\in [x_{i}+(d-g),x_{i}+(d+g)] ) $
交上去发现$T$了，一看，二分域太大。
```cpp
#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）：
考虑以保证对于每两点间距离能跳过去作为二分边界，交上去证明我错了。
```cpp
#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代码，交上去过了。
```cpp
#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，二分也没有什么骚操作，就是边界这种东西……
好像摸到一点意思：求最大和的时候，负权对于答案的最低要求没有贡献，所以二分上界是要确保能取到所有正权。
也就是说，“最优答案”和“合法答案/最低要求/搜索边界”需要的数据不太一样，经常会用贪心思路找边界。
（错了再改）
by Hansue @ 2020-05-28 17:57:34
呃，我的意思是这是我去年5.28写完了这题之后在cnblog上发的题解。
by Hansue @ 2020-05-28 17:58:46