沼泽穿越：最少体力消耗算法

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

题目描述

你在森林的一条小路上行走, 每个点可以看做一个坐标点, 每个位置可以是陆地, 也可以是沼泽, 你不能掉入沼泽, 否则会开席. 你可以走到相邻的陆地上, 不需要花费体力, 如果你想跳跃沼泽, 比如从 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 <algorithm>
#include <climits>
using namespace std;
int minCost(vector<int>& path) {
int n = path.size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for (int i = 1; i < n; i++) {
if (path[i] == 0) {
dp[i] = min(dp[i], dp[i - 1] + 1);
}
if (i >= 2 && path[i] == 0 && path[i - 1] == 0) {
dp[i] = min(dp[i], dp[i - 2] + 2);
}
if (i >= 3 && path[i] == 0 && path[i - 1] == 0 && path[i - 2] == 0) {
dp[i] = min(dp[i], dp[i - 3] + 3);
}
}
return dp[n - 1];
}
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];
}
int min_cost = minCost(path);
cout << min_cost << endl;
}
return 0;
}