欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-04 18:51:13
...

传送门

题目

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]));
}
}

相关标签: 算法