Yuki 409 ダイエット ( Decision Monotonous, DP )
題意:
有 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 ) ) )