Yuki 409 ダイエット ( Decision Monotonous, DP )

No.409 ダイエット - yukicoder

題意：
有 N 天，第 i 天有重量 D[ i ] 單位的甜甜圈可以吃。你現在的重量是 W 單位，你想減肥，所以每天你可以選擇吃或不吃。如果吃了，你的體重就會增加吃掉的重量並歸零壓力值，否則你會減去 A 單位的重量但同時增加一個單位的壓力值。每天吃完或不吃完並結算壓力值後，你的重量會再增加 B * 當前的壓力值。問 N 天後最低可能的體重。

制約：
1≤N≤3e5
0≤A,B,W≤1e6
0≤Di≤1e6

解法：
寫斜率優化不知道為什麼 WA，放棄。
因為可以用斜率優化解，而且有單調遞減斜率，所以有決策單調性，水一波。
另外，算一下可以發現最佳情況至多會連續不吃 1000 天，所以利用這個閥值直接寫也可以，如下：
#108739 No.409 ダイエット - yukicoder

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

from collections import deque

N, A, B, W = map( int, input().split() )
D = list( map( int, input().split() ) )
dp = [ 0 for i in range( N + 1 ) ]

def get_cost( x, rb ):
  d = rb - x - 1
  return dp[ x ] + d * ( d + 1 ) // 2 * B - d * A + D[ rb - 1 ]

dq = deque()
dp[ 0 ] = W
dq.append( [ 0, 1, N ] )
for i in range( 1, N + 1 ):
  while dq[ 0 ][ 2 ] < i:
    dq.popleft()
  dp[ i ] = get_cost( dq[ 0 ][ 0 ], i )
  while len( dq ):
    x, lb, rb = dq[ len( dq ) - 1 ]
    if get_cost( x, lb ) >= get_cost( i, lb ):
      dq.pop()
      if len( dq ):
        dq[ len( dq ) - 1 ][ 2 ] = N
    else:
      break
  best = -1
  x, lb, rb = dq[ len( dq ) - 1 ][ 0 ], i + 1, N
  while lb <= rb:
    mid = lb + rb >> 1
    if get_cost( x, mid ) >= get_cost( i, mid ):
      best = mid
      rb = mid - 1
    else:
      lb = mid + 1
  if best == -1: continue
  dq[ len( dq ) - 1 ][ 2 ] = best - 1
  dq.append( [ i, best, N ] )

print( min( dp[ i ] + ( N - i ) * ( N - i + 1 ) // 2 * B - ( N - i ) * A for i in range( N + 1 ) ) )