方法思路

为了求解小红到达n号国家的最少花费，我们可以采用动态规划的方法。动态规划的状态表示当前国家的最小花费，转移时考虑在当前国家购买粮食或从之前国家运输粮食的最小花费。

1. 动态规划状态定义：dp[i]表示到达第i个国家时的最小花费。
2. 状态转移：
   • 如果当前国家的粮食价格nums[i]小于等于前一个国家的最小花费加1（运输费用），则dp[i] = nums[i]。
   • 否则，dp[i] = dp[i-1] + 1，表示从之前国家运输粮食。
3. 初始化：dp[0] = nums[0]，因为初始时必须在第一个国家购买粮食。
4. 结果计算：累加所有dp[i]的值即为总最小花费。

代码实现

Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        
        int prev = Integer.parseInt(input[0]);  // 前一个国家的最小花费
        long ans = 0;  // 总花费
        
        for (int i = 1; i < n; i++) {
            int currentPrice = Integer.parseInt(input[i]);
            ans += prev;  // 累加前一个国家的花费
            
            // 更新当前国家的花费
            if (currentPrice <= prev + 1) {
                prev = currentPrice;
            } else {
                prev = prev + 1;
            }
        }
        
        bw.write(ans + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
}

Python

def main():
    n = int(input())  # 输入国家数量
    nums = list(map(int, input().split()))  # 输入粮食价格
    
    # dp[i]表示前面所有的城市到第i格最小的补给
    dp = nums[:]  # 初始化dp数组，复制nums
    
    ans = 0
    for i in range(1, n):
        if nums[i] <= dp[i - 1] + 1:
            dp[i] = nums[i]
        else:
            dp[i] = dp[i - 1] + 1
        ans += dp[i - 1]
    
    print(ans)

if __name__ == "__main__":
    main()

C++

#include<iostream>
using namespace std;
using LL = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    int prev = 0;
    cin >> prev;  // 读取第一个国家的粮食价格
    
    LL ans = 0;
    for (int i = 1; i < n; ++i) {
        int current;
        cin >> current;  // 读取当前国家的粮食价格
        
        ans += prev;  // 累加前一个国家的花费
        
        // 更新当前国家的最小花费
        if (current <= prev + 1) {
            prev = current;
        } else {
            prev = prev + 1;
        }
    }
    
    cout << ans << '\n';
    return 0;
}