Educational Codeforces Round 95 (Rated for Div. 2)C. Mortal Kombat Tower（DP）

题意：给你一个数n，下面紧接着给你n个数，由0到1组成，如果为1则说明此boss较难，0则较简单，你的朋友每通过一个较难的boss时需使用一个跳跃点，你的朋友先手每次能杀死1或2个boss紧接着是你一直到n个boss杀完，问：至少需要多少个跳跃点.

思路：两种情况：

定义两个参数：i 代表第几个怪物，1代表我击杀怪物，0代表队友击杀怪物。

然后分两种情况：

1. 如果当前这个怪物是我杀的，那么 $d p [i] [1] = m i n (d p [i - 1] [0], d p [i - 2] [0])$

$d p [i] [1] = m i n (d p [i - 1] [0], d p [i - 2] [0])$ $d p [i] [1] = m i n (d p [i - 1] [0], d p [i - 2] [0])$ $d p [i] [1] = m i n (d p [i - 1] [0], d p [i - 2] [0])$

最后 dp[i][1] 和 $d p [i] [1] = m i n (d p [i - 1] [0], d p [i - 2] [0])$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const double eps=1e-7;
const ll INF=1e9+10;
int main()
{
    int t;
    int n;
    ll a[N];
    ll dp[N][2];
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1; i<=n; ++i)
        {
            cin>>a[i];
            dp[i][0]=INF;
            dp[i][1]=INF;
        }
        dp[1][0]=a[1];
        dp[2][0]=a[1]+a[2];
        dp[2][1]=a[1];
        for(int i=3; i<=n; ++i)
        {
            dp[i][1]=min(dp[i-1][0],dp[i-2][0]);  //如果该这个怪物是我打
            dp[i][0]=min(dp[i-1][1]+a[i],dp[i-2][1]+a[i-1]+a[i]);//如果这个怪物是对队友打
        }
        printf("%d
",min(dp[n][0],dp[n][1]));
    }

    return 0;
}

View Code