AcWing 302. 任务安排3 凸包优化DP
原题链接
困难
作者:
皓首不倦
,
2020-07-31 18:22:57
,
所有人可见
,
阅读 724
from collections import deque
N, S = map(int, input().split())
St = [0] * N
Sc = [0] * N
for i in range(N):
St[i], Sc[i] = map(int, input().split())
for i in range(1, N):
St[i], Sc[i] = St[i] + St[i-1], Sc[i] + Sc[i-1]
# 凸包的下边界
que = deque()
# 因为Sc(-1) = 0, dp(-1) = 0, 一开始凸包里面就有这么一个初始点
que.append((-1, 0, -0x7fffffff)) # 三元组结构(下标i, dp(i), 和图标序列前一个点之间直线的斜率)
dp = [0] * N
for i in range(N):
cur_k = S + St[i]
n = len(que)
l, r = 0, n-1
pos = -0x7fffffff
while l <= r:
mid = l + (r-l) // 2
if que[mid][2] >= cur_k:
pos = mid
r = mid - 1
else:
l = mid + 1
pos = n-1 if pos == -0x7fffffff else pos-1
selected_k = que[pos][2]
j = que[pos][0]
if j == -1:
dp[i] = St[i]*Sc[i] + S*Sc[N-1]
else:
dp[i] = dp[j] - cur_k * Sc[j] + (St[i]*Sc[i] + S*Sc[N-1])
# 根据凸包下边界性质,比较斜率,更新凸包的下边界
last_k = 0
if len(que) > 1:
while len(que) > 1:
j = que[-2][0]
Sc_val = 0 if j == -1 else Sc[j]
if Sc[i] - Sc_val != 0:
last_k = (dp[i] - que[-2][1]) / (Sc[i] - Sc_val)
else:
if dp[i] - que[-2][1] < 0:
last_k = -0x7fffffff
elif dp[i] - que[-2][1] > 0:
last_k = 0x7fffffff
else:
last_k = 0
if que[-1][2] >= last_k:
que.pop()
else:
break
j = que[-1][0]
Sc_val = 0 if j == -1 else Sc[j]
if Sc[i] - Sc_val != 0:
last_k = (dp[i] - que[-1][1]) / (Sc[i] - Sc_val)
else:
if dp[i] - que[-1][1] < 0:
last_k = -0x7fffffff
elif dp[i] - que[-1][1] > 0:
last_k = 0x7fffffff
else:
last_k = 0
que.append((i, dp[i], last_k))
print(dp[N-1])