【AtCoder Regular Contest 072 E】Alice in linear land | Mrsrz's blog

动态规划。

题目大意：

有一个数轴，终点为 $D$。给定 $d_1,d_2,d_3,\ldots,d_n$。一个机器人从原点出发，第 $i$ 次行动会向终点方向走 $d_i$ 个单位，如果停下的位置离终点反而更远则不行动。

有 $m$ 个询问，每次给出 $k$，你可以将 $d_k$ 改成任意整数。问是否存在一种方案，使得机器人依次执行完所有指令以后还不能到终点。

题解：

每次给出 $k$，在到达 $k$ 之前的情况是不会变的。

令 $f_{i,j}$ 表示第 $i$ 次执行前在位置 $j$，最后是否能到终点。

我们只需要知道在第 $k$ 次行动是否能走到一个不能到达终点的方案即可。

事实上我们只需要关心最小的不能到达终点的点。

我们记录 $g_i$ 表示第 $i$ 次行动，$0\sim g_i$ 位置都能到达终点。

然后往前推。如果 $2g_{i+1}+1\geq d_i$，则 $g_i$ 必须要往外 $d_i$ 格，否则可以不动。

之后询问时直接比较大小即可。

Code：

#include<cstdio>
#include<cstdlib>
int F[500005],A[500005];
int n,i;
int main(){
    scanf("%d%d",&n,A);
    for(i=1;i<=n;++i)scanf("%d",A+i);
    F[n]=A[n]==1;
    for(i=n-1;i;--i)F[i]=F[i+1]*2+1>=A[i]?F[i+1]+A[i]:F[i+1];
    for(i=1;i<=n;++i)A[i]=abs(A[i-1]-A[i])<A[i-1]?abs(A[i-1]-A[i]):A[i-1];
    scanf("%d",&n);
    while(n--)scanf("%d",&i),puts(A[i-1]>F[i+1]?"YES":"NO");
    return 0;
}