C++ 沼泽地穿越问题：最少体力消耗算法

众所周知，掉入沼泽地可不是一件好玩的事情～

题目描述

你在森林的一条小路上行走，每个点可以看做一个坐标点，每个位置可以是陆地，也可以是沼泽，你不能掉入沼泽，否则会开席。你可以走到相邻的陆地上，不需要花费体力，如果你想跳跃沼泽，比如从 x 位置跳跃到 x+d 位置，你需要花费 d 的体力。不过不幸的是，你最多只能跳跃一次。

现在你想知道你需要花费最少多少体力可以穿越这条危险的小路。

数据格式

输入格式 第一行输入一个整数 t，表示有 t 组数据。

接下来每组数据，第一行输入一个整数 n，表示这条路的长度，接下来 n 个整数 0 或 1，用 0 表示沼泽， 1 表示陆地，确保 1, n 位置为陆地。

输出格式 输出 t 行，每行一个整数表示最少花费多少金币。

样例

输入数据 1

3
5
1 1 1 1 1
6
1 0 1 0 0 1
8
1 1 1 0 0 0 1 1

输出数据 1

0
5
4

数据范围

1 <= t <= 100
1 <= n <= 1000

C++ 代码实现

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        vector<int> path(n);
        for (int i = 0; i < n; i++) {
            cin >> path[i];
        }
        
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        
        for (int i = 1; i < n; i++) {
            if (path[i] == 1) {
                dp[i] = min(dp[i], dp[i-1]);
            }
            if (i > 1 && path[i] == 1 && path[i-1] == 0) {
                dp[i] = min(dp[i], dp[i-2] + 1);
            }
        }
        
        cout << dp[n-1] << endl;
    }
    
    return 0;
}

代码解析

输入数据: 首先，读取输入数据，包括数据组数 t 和每组数据的长度 n 以及路径信息 path。
动态规划: 使用动态规划（DP）来解决这个问题，定义 dp[i] 表示到达位置 i 所需的最小体力消耗。
初始化: 初始化 dp[0] 为 0，因为起点无需消耗体力。
迭代: 从位置 1 开始遍历路径，对于每个位置 i，考虑两种情况：
- 如果当前位置 i 是陆地（path[i] == 1），则可以选择从前一个位置 i-1 走过来，消耗的体力与 dp[i-1] 相同。
- 如果当前位置 i 是陆地，并且前一个位置 i-1 是沼泽，则可以选择从位置 i-2 跳跃过来，消耗的体力为 dp[i-2] + 1。
结果: 最终，dp[n-1] 就表示到达终点所需的最小体力消耗。

总结

本页面提供了一个使用 C++ 解决沼泽地穿越问题的完整代码示例，并详细解释了动态规划算法的思路和实现细节。希望这份代码和解析能帮助你更好地理解动态规划的应用，并能帮助你解决类似的问题。