MarsCode-徒步

问题描述

小明想从A徒步到B，总路程需要M天，路程中为了确保安全，小明每天需要消耗1份食物。

在起点及路程当中，零星分布着N个补给站，可以补充食物，不同补给站的食物价格可能不同。

请问小明若要安全完成徒步，最少需要花费多少钱呢？

输入格式

第一行为两个正整数M、N，代表总路程M天，补给站个数N

接下来N行，每行有两个非负整数A、B代表一个补给站，表示第A天经过该补给站，每份食物的价格为B元。

A是从0开始严格递增的，即起点一定有补给站，补给站是按位置顺序给出的，且同一个位置最多有一个补给站。

输出格式

输出一个整数，表示最少花费的金额

输入样例

5 4  
0 2  
1 3  
2 1  
3 2  

输出样例

7

说明：在第0天买2份食物，在第2天买3份食物，共花费7元

数据范围

- 30%的数据，N <= M <= 100， 0 <= A < M， 0 <= B <= 1000

- 80%的数据，N <= M <= 10000， 0 <= A < M， 0 <= B <= 1000

- 100%的数据，N <= M <= 1000000， 0 <= A < M， 0 <= B <= 1000

解答

采用动态规划求解
$$
dp[day][food] =min{dp[day-1][food+1], dp[day-1][food]+price, dp[day-1][food-1]+price*2 + …}
$$
Python代码求解如下

def solution(n, k, p):
    # Edit your code here
    dp = [[float('inf') for _ in range(n+2)] for _ in range(n+2)]
    for i in range(n+1):
        dp[0][i] = 0
    # 若第1天有补给站，购买起始物资
    if p[0][0] == 0:
        for food in range(1, n+1):
            dp[1][food] = food * p[0][1]
    # 第2天到第n天
    for day in range(2, n+1):
        for food in range(1, n+1):
            flag = 0
            # 遇到补给站
            for station_day, station_price in p:
                if day == station_day+1:
                    flag = 1
                    for num in range(food+1):
                        dp[day][food] = min(dp[day][food], dp[day-1][food-num+1]+num * station_price)
            # 无补给站
            if flag == 0:
                dp[day][food] = dp[day-1][food+1]
    return dp[n][1]


if __name__ == "__main__":
    # Add your test cases here

    print(solution(5, 4, [[0, 2], [1, 3], [2, 1], [3, 2]]) == 7)