今天我们的考试就考到了这道题，在考场上就压根没有思路，我知道它是一道dp的题，但因为太弱还是写不出来。
下来评讲的时候知道了一些思路，是dp加上二分查找的方式，还能够用单调队列优化。
但看了网上的许多代码和博客都觉得不太明白单调队列的应用，看来真的还是太菜了。
单调队列掌握不熟练(其实什么也不知道了，虽然之前是讲过的)
那就换一种思路，不用单调队列，二分+dp其实就能搞出来。
怎么能看出这道题是二分的呢？其实因为可以分析数据看出，花费的数量是成单调递增的，满足二分是单调性的情况，所以我们可以用二分答案的形式。
主函数里我就用了一个二分答案
int main()
{
scanf("%lld%lld%lld",&n,&d,&k);
for(ll i=;i<=n;i++)
{
scanf("%lld%lld",&a[][i],&a[][i]);//输入距离和费用
}
ll l=;//从零开始
ll r=;//随便定的一个右端点值
ll mid;
while(l<=r)//二分答案模板
{
mid=(l+r)>>;
if(check(mid))
{
ans=mid;//最优解是mid
r=mid-;
}
else
{
l=mid+;
}
}
}
二分当然还少不了check函数
那么我们的dp也就包含在check函数当中
然后呢
从题中就可以读出改造后机器人可以行走的步数的最小值d-g以及最大值d+g，就大概有了一个范围；
那既然是dp，就应该使用状态转移
在这里其实又可以有两种转移的方式
1.从当前点开始像前面转移，就可已从前面找可以使它跳动的距离最大的值，并且这个值又在范围内
转移方程(最优值) f[当前点]=max(f[从当前点往前面找]+a[1][当前点](当前点的价值)，f[当前点](已经保存的最优值));
当这个最优值比预期的k大于或等于时
就说明存在这样的一个修改值满足条件
之后就是二分答案的查找
代码如下
bool check(int x)
{
ll left=d-x;
if(d-x<)
{
left=;//默认的最小值为1，避免越界
}
ll right=d+x;
memset(f,-,sizeof(f));//初始化数组为一个特别小的数
f[]=;
for(ll i=;i<=n;i++)
{
for(ll j=i-;j>=;j--)//从当前点之前的开始找
{
if(a[][i]-a[][j]<left)//如果距离比最小的值都小，就忽略可以不修改
{
continue;
}
if(a[][i]-a[][j]>right)//如果最大的距离都满足不了，结束不用找
{
break;
}
f[i]=max(f[i],f[j]+a[][i]);//转移方程
if(f[i]>=k)//满足条件
{
return true;
}
}
}
return false;
}
2.从当前的格子向后转移，顺着找最优解
这样又怎么办呢？
相信大佬秒看就知道了
当前的点就是从0开始，在n之前的所有点
转移方程为f[后面的点]=max(f[后面的点](已经储存的最优解),f[当前点](当前最优解)+a[1][后面点]);
代码就在下面了
bool check(int x)
{
ll left=d-x;
if(d-x<)
{
left=;
}
ll right=d+x;
memset(f,-,sizeof(f));//初始化不用说
f[]=;/没有走时的最优解为0
for(ll i=;i<n;i++)//有没有等于号都无所谓了
{
for(ll j=i+;j<=n;j++)//从当前点后面的一个点开始，也可以就从i点来
{
if(a[][j]-a[][i]<left)
{
continue;
}
if(a[][j]-a[][i]>right)
{
break;
}
f[j]=max(f[j],f[i]+a[][j]);//转移方程向后面转移
if(f[j]>=k)
{
return true;
}
}
}
return false;
}
完整代码1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,d,k,ans;
ll a[][];
ll f[];
bool check(int x)
{
ll left=d-x;
if(d-x<)
{
left=;
}
ll right=d+x;
memset(f,-,sizeof(f));
f[]=;
for(ll i=;i<=n;i++)
{
for(ll j=i-;j>=;j--)
{
if(a[][i]-a[][j]<left)
{
continue;
}
if(a[][i]-a[][j]>right)
{
break;
}
f[i]=max(f[i],f[j]+a[][i]);
if(f[i]>=k)
{
return true;
}
}
}
return false;
}
int main()
{
scanf("%lld%lld%lld",&n,&d,&k);
for(ll i=;i<=n;i++)
{
scanf("%lld%lld",&a[][i],&a[][i]);
}
ll l=;
ll r=;
ll mid;
while(l<=r)
{
mid=(l+r)>>;
if(check(mid))
{
ans=mid;
r=mid-;
}
else
{
l=mid+;
}
}
printf("%lld",ans);
return ;
}
完整代码2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,d,k,ans;
ll a[][];
ll f[];
bool check(int x)
{
ll left=d-x;
if(d-x<)
{
left=;
}
ll right=d+x;
memset(f,-,sizeof(f));
f[]=;
for(ll i=;i<=n;i++)
{
for(ll j=i;j<=n;j++)
{
if(a[][j]-a[][i]<left)
{
continue;
}
if(a[][j]-a[][i]>right)
{
break;
}
f[j]=max(f[j],f[i]+a[][j]);//转移方程从前一个格子转移过来
if(f[j]>=k)
{
return true;
}
}
}
return false;
}
int main()
{
scanf("%lld%lld%lld",&n,&d,&k);
for(ll i=;i<=n;i++)
{
scanf("%lld%lld",&a[][i],&a[][i]);
}
ll l=;
ll r=;
ll mid;
while(l<=r)
{
mid=(l+r)>>;
if(check(mid))
{
ans=mid;
r=mid-;
}
else
{
l=mid+;
}
}
printf("%lld",ans);
return ;
}
好了，这道题算是比较明白了，没有任何优化，在洛谷上也是可以AC的
之后搞懂了单调队列优化，再回头来改的更完善
如果有不足之处，就请大佬来为本蒟蒻提出来
就是这样