Educational Codeforces Round 95 (Rated for Div. 2)C. Mortal Kombat Tower【dp】

传送门

题目

输入
6
8
1 0 1 1 0 1 1 1
5
1 1 1 1 0
7
1 1 1 1 0 0 1
6
1 1 1 1 1 1
1
1
1
0
输出
2
2
2
2
1
0

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

思路：dp模板题，每人每次有两个选择，即上个人的两个状态，取最小的即可

AC code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<sstream>
#include<queue>
#include<stack>
using namespace std;
const int inf=0x3f3f3f3f;
int a[210000][2],b[210000];
int main()
{
    ios::sync_with_stdio(0);
    int t,n;
cin>>t;
while(t--)
{
    cin>>n;
    memset(a,inf,sizeof(a));
    for(int i=1;i<=n;i++)
      cin>>b[i];
      a[0][0]=0;
      a[1][1]=b[1];
      for(int i=2;i<=n;i++)
      {
          a[i][0]=min(a[i-1][1],a[i-2][1]);
          a[i][1]=min(a[i-1][0]+b[i],a[i-2][0]+b[i-1]+b[i]);
      }
      printf("%d\n",min(a[n][1],a[n][0]));
}
}