QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#827515 | #9552. The Chariot | LilyWhite | RE | 0ms | 0kb | Python3 | 1.4kb | 2024-12-23 00:41:32 | 2024-12-23 00:41:33 |
Judging History
answer
import sys
def minimal_travel_cost(A, B, C, X, Y, D):
# Maximum segment length is X + Y
max_segment = X + Y
# Precompute cost for each possible segment length
cost = [0] * (max_segment + 1)
for k in range(1, max_segment + 1):
if k <= X:
cost[k] = A
elif k <= X + Y:
cost[k] = A + B * (k - X)
else:
cost[k] = A + B * Y + C * (k - X - Y)
# Initialize DP array
INF = float('inf')
dp = [INF] * (D + 1)
dp[0] = 0 # Cost to travel 0 meters is 0
# Fill DP array
for i in range(1, D + 1):
# Iterate over all possible segment lengths
for k in range(1, max_segment + 1):
if i - k >= 0:
if dp[i - k] + cost[k] < dp[i]:
dp[i] = dp[i - k] + cost[k]
return dp[D]
def main():
import sys
input = sys.stdin.read
data = input().split()
T = int(data[0])
idx = 1
results = []
for _ in range(T):
A = int(data[idx])
B = int(data[idx+1])
C = int(data[idx+2])
X = int(data[idx+3])
Y = int(data[idx+4])
D = int(data[idx+5])
idx +=6
cost = minimal_travel_cost(A, B, C, X, Y, D)
results.append(str(cost))
print('\n'.join(results))
if __name__ == "__main__":
main()
详细
Test #1:
score: 0
Dangerous Syscalls
input:
5 160 27 41 3 12 3 160 27 41 3 12 4 160 27 41 3 12 99 1 999 999 1 99 999 999 999 1 1 99 9999999999999999