题目背景众所周知 掉入沼泽地可不是一件好玩的事情~题目描述你在森林的一条小路上行走 每个点可以看做一个坐标点 每个位置可以是陆地 也可以是沼泽 你不能掉入沼泽 否则会开席 你可以走到相邻的陆地上 不需要花费体力 如果你想跳跃沼泽 比如从 �x 位置跳跃到 �+�x+d 位置 你需要花费 �d 的体力 不过不幸的是 你最多只能跳跃一次现在你想知道你需要花费最少多少体力可以穿越这条危险的小路数据格式输

#include #include #include 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;