上海网站建设 微信开发公司,好的h5网站,无锡做网站选优易信,现在出入山西最新规定前言
链接#xff1a; https://www.luogu.org/record/show?rid7915892 这就是之前普及组的第四题… 大意
有n个格子#xff0c;每个格子有价值。机器人有固定的跳跃距离d#xff0c;用k个金币改进的话#xff0c;就可以让跳跃距离在d-k到dk之间#xff0c;不过至少要…前言
链接 https://www.luogu.org/record/show?rid7915892 这就是之前普及组的第四题… 大意
有n个格子每个格子有价值。机器人有固定的跳跃距离d用k个金币改进的话就可以让跳跃距离在d-k到dk之间不过至少要往前跳1个单位长度每次都必须跳到格子上。要求超过需要的价值求需要消耗的最少金币。 解题思路
二分所需金币数然后 dpf[i]f[i]f[i]表示跳到第i个格子最大价值然 后
f[i]f[max:f[l]...f[r];]c[i]f[i]f[max:f[l]...f[r];]c[i]
f[i]=f[max:f[l]...f[r];]+c[i]这个简单的方程就不解释了然后单调队列维护max:f[l]...f[r];max:f[l]...f[r];max:f[l]...f[r];代码
#includecstdio
#includealgorithm
#includecstring
using namespace std;
int f[500001],x[500001],c[500001],q[500001];
int n,d,k,l,r,mid;
bool answer()
{memset(f,-1,sizeof(f));//初始化f[0]0;int head1,tail0,j0;int farstdmid,sdmax(1,d-mid);//前后跳跃距离for (int i1;in;i){while (x[j]sdx[i])//可以跳到改格{while (headtailf[j]f[q[tail]]) tail--;q[tail]j;j;//加入队列并维护}while (headtailx[q[head]]farstx[i]) head;//将已经无法跳到的退出if (headtailf[q[head]]!-2333333) f[i]f[q[head]]c[i];else f[i]-2333333;//密钥表示无法到达if (f[i]k) return 1;//已经可以退出}return 0;
}
int main()
{scanf(%d%d%d,n,d,k);for (int i1;in;i)scanf(%d%d,x[i],c[i]);l1;rx[n];while (lr)//二分{mid(lr)/2;if (answer()) rmid-1;else lmid1;}if (lx[n]) printf(-1);else printf(%d,l);
}
