【ARC072E】Alice in linear land DP

xiaoxiao2021-02-28  4

题目大意

  有一个人要去直线上 lm 远处的地方,他会依次给他的机器发出 n 个指令。第i个指令为 di 。他的机器收到一个指令 x 后,如果向目的地方向前进xm后比当前离目的地更近,就会向前移动 xm ,否则什么都不会做。

  现在,给你 q 个询问,第i个询问为 ai ,问你能不能改变 dai ,使得这个人不能到达目的地。你可以决定把 dai 改成什么数。

   n,q500000,1di109

题解

  首先我们先算出执行前面 i 个指令后离终点的距离ci

  暴力的做法是用DP算出 gi,j :执行后面 i ~n的指令,离终点的距离为 j ,执行完后能不能到达终点。

  然后就会发现一旦出现一个0,后面的 1 就会无意义。(因为可以修改成直接走到0这里)

  那么我们只需要维护前面有多少个 1

  fi表示执行后面 i ~n的指令,前面 gi,0 ~ g0,fi 全部是 1 gi,fi 1 0

  那么如果di2fi 1 1,那么 fi=fi+1+di 。否则 fi=fi+1

  可以发现,第一种情况 0 ~fi之间不会有空洞。

  询问 ai 时直接判断 cai1 是不是比 fai+1 大。这样直接走到 fai+1+1 就可以了。

  时间复杂度: O(n)

代码

#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<ctime> #include<utility> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; int n,q; ll m; ll d[500010]; ll c[500010]; ll f[500010]; void rd(int &s) { int c; while((c=getchar())<'0'||c>'9'); s=c-'0'; while((c=getchar())>='0'&&c<='9') s=s*10+c-'0'; } void rd(ll &s) { int c; while((c=getchar())<'0'||c>'9'); s=c-'0'; while((c=getchar())>='0'&&c<='9') s=s*10+c-'0'; } int abs(int x) { return x>0?x:-x; } void yes() { putchar('Y'); putchar('E'); putchar('S'); putchar('\n'); } void no() { putchar('N'); putchar('O'); putchar('\n'); } int main() { #ifdef DEBUG freopen("a.in","r",stdin); freopen("a.out","w",stdout); #endif scanf("%d%lld",&n,&m); int i; ll x; c[0]=m; for(i=1;i<=n;i++) { rd(d[i]); c[i]=min(c[i-1],abs(c[i-1]-d[i])); } f[n+1]=0; for(i=n;i>=1;i--) { f[i]=f[i+1]; if(d[i]<=2*f[i+1]+1) f[i]=max(f[i],f[i+1]+d[i]); } scanf("%d",&q); for(i=1;i<=q;i++) { rd(x); if(c[x-1]>f[x+1]) yes(); else no(); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-1749982.html

最新回复(0)