ARC 072 E - Alice in linear land ( DP )

E: Alice in linear land - AtCoder Regular Contest 072 | AtCoder

題意：
有一個車子在數線上的原點。目標是 D。依序有 N 個操作，d[ i ] 代表第 i 次操作的參數。每次操作將會使車子向目標的方向前進 d[ i ]，但特別地，如果操作後不會接近，則該次操作無效。有 Q 筆彼此獨立的詢問，問若修改第 q[ i ] 個操作為任意正整數，是否可以使得車子永遠不會到達目標。

制約：
1≦N≦5e5
1≦Q≦5e5
1≦D≦1e9
1≦di≦1e9(1≦i≦N)
1≦qi≦N(1≦i≦Q)
di,Dは整数である

解法：
先計算 dis[ i ]，代表第 i 次操作結束後，離目標的距離。
觀察到車子只會離目的地越來越近，一旦接近就不會變遠。
若當前的距離為 x，那麼修改後等價是改成距離為 [ 0, x ] 中一個整數。
dp[ i ]：在進行第 i 次操作前，最小的安全距離，使得若當前為這個距離以上，將來都不會到達目標。
邊界：dp[ N + 1 ] = 1 ( 1 base )
轉移如下：
__若 d[ i ] // 2 ≥ dp[ i + 1 ]：
____那麼這次操作沒有意義，所以 dp[ i ] = dp[ i + 1 ]
__否則：
____dp[ i ] = dp[ i + 1 ] + d，因為如果 dp[ i ] < dp[ i + 1 ] + d，操作後當前距離一定會少於 dp[ i + 1 ] 然後到達目標。
對一個修改 u，若且唯若 dis[ u ] < dp[ u + 1 ] 則一定會到達目標。

時間 / 空間複雜度：
O( N + Q )

N, D = map( int, input().split() )
d = list( map( int, input().split() ) )
Q = int( input() )
q = list( map( lambda x: int( x ) - 1, input().split() ) )

dis = [ 0 for i in range( N + 1 ) ]
dis[ 0 ] = D
for i in range( N ):
  dis[ i + 1 ] = min( dis[ i ], abs( dis[ i ] - d[ i ] ) )

dp = [ 0 for i in range( N + 1 ) ]
dp[ N ] = 1
for i in range( N - 1, -1, -1 ):
  if dp[ i + 1 ] <= d[ i ] // 2:
    dp[ i ] = dp[ i + 1 ]
  else:
    dp[ i ] = dp[ i + 1 ] + d[ i ]

for qi in range( Q ):
  print( [ "NO", "YES" ][ dis[ q[ qi ] ] >= dp[ q[ qi ] + 1 ] ] )