题解：AT_arc072_c [ARC072E] Alice in linear land
binomial
·
·
题解
题目传送门
0.前言
模拟赛里面考到了......当时想的优先队列维护，不出意外的死了......
参考了这位 dalao 的题解
1.暴力
相信所有人看到这道题，都能想到一个显然的 DP。
状态表示：dp[i][j] 表示后 i 项能否在 d=j 的情况下走到终点。1 表示可以，反之不行。
转移方程式如下：
原因：当用后 $i+1$ 种操作能在 $j-d[i]$ 的情况下走到终点时，此时先走 $d[i]$ 再走 $j-d[i]$ 即可完成 $d=j$ 的情况。需要注意必须 $d[i] \le j$，不然就走过了。
$dp[i][j]=dp[i+1][d[i]-j]$（当 $j < d[i] \le 2 \times j$ 时）
原因：当用后 $i+1$ 种操作能在 $d[i]-j$ 的情况下走到终点时，此时先走 $d[i]$，越过终点。此时到达离终点 $d[i]-j$ 的位置。再往回走 $d[i]-j$ 即可完成即可完成 $d=j$ 的情况。需要注意必须 $j < d[i] \le 2 \times j$，不然就走不过或者大于了原距离。
$dp[i][j]=dp[i+1][j]$（当 $2 \times j < d[i]$ 时）
原因：显然如果走了 $d[i]$ 的距离会比原距离还要大，所以不走，只能让后 $i+1$ 种操作走 $j$ 的距离。
对于询问，不难发现如果询问第 $i$ 个位置对 $i$ 以前的位置走到的位置是无关的。对于对 $i$ 及以后的位置，由于 $i$ 可以随便改，所以只要离终点的距离是在前 $i$ 个位置离终点的位置以内的距离，都是可以的。（如果大于不会移动），此时我们设前 $i$ 个位置离终点的距离为 $x$，那么只有 $i+1$ 及以后的位置可以处理 $j \in 0 \sim x$ 的所有情况，才输出 `NO`。
显然，这是一个 $O(nD)$ 的做法，尝试优化。
## 2.优化
观察到，我们仅需找到 $dp[i+1][j\in 0 \sim x]$ 中是否存在 $0$ 即可。观察到 $dp[i+1]$ 中 $j$ 是越小越容易影响答案的（因为查询范围最小都是 $0$），所以我们希望仅维护 $dp[i]$ 表示 $dp[i][j]$ 中最小的 $j$。我们来尝试表示一下状态转移方程式。
$dp[i]=dp[i+1]$（当 $d[i] \ge 2 \times dp[j+1]$ 时，对应第三个方程式）
$dp[i]=d[i]-dp[i+1]$（当 $d[i] > 2 \times dp[j+1]$ 时，对应第二个方程式）
$dp[i]=dp[i+1]+d[i]$（当 $d[i] \le dp[i+1]+d[i]$ 时，由于这显然成立，所以等于无条件，对应第一个方程式）
核心逻辑：$dp[i]=dp[i][minj]=$ 转移所用 $j$。
根据上述三个式子转移即可。
对于询问，只需判断 $dp[i]$ 与 $x$ 的大小关系即可。
## 3.代码
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,d,a[500005],pl,q,uo,pre[500005],dp[500005],now;
bool can[500005];
int main(){
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(abs(now-d)>abs(now+a[i]-d)){
now+=a[i];
}
if(abs(now-d)>abs(now-a[i]-d)){
now-=a[i];
}
pre[i]=abs(now-d);//计算x
}
pre[0]=d;
dp[n+1]=1;
for(int i=n;i>=1;i--){
if(a[i]>=2*dp[i+1]){
dp[i]=dp[i+1];//方程1
if(a[i]>2*dp[i+1]){
dp[i]=min(dp[i],a[i]-dp[i+1]);//方程2
}
}
else{
dp[i]=dp[i+1]+a[i];//方程3，因为明显方程1优于方程3，所以放在else里
}
}
scanf("%d",&q);
can[n+1]=0;
for(int i=1;i<=q;i++){
scanf("%d",&uo);
if(dp[uo+1]<=pre[uo-1]){//判断
printf("YES\n");
}
else{
printf("NO\n");
}
}
return 0;
}
//6
```