Educational Codeforces Round 95 (Rated for Div. 2)C. Mortal Kombat Tower【dp】
程序员文章站
2022-06-04 18:51:13
...
题目
输入
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]));
}
}
推荐阅读
-
Educational Codeforces Round 85 (Rated for Div. 2) C. Circle of Monsters(前缀和 预处理 贪心)
-
Educational Codeforces Round 99 (Rated for Div. 2) C. Ping-pong
-
C. Mortal Kombat Tower(动态规划)Educational Codeforces Round 95 (Rated for Div. 2)
-
Educational Codeforces Round 88 (Rated for Div. 2)C. Mixing Water[题解](数学)
-
Educational Codeforces Round 95 (Rated for Div. 2)C. Mortal Kombat Tower【dp】
-
Educational Codeforces Round 67 (Rated for Div. 2) E. Tree Painting(树形dp)
-
Educational Codeforces Round 77 (Rated for Div. 2) E. Tournament (DP)
-
Educational Codeforces Round 39 (Rated for Div. 2) D. Timetable - dp分组背包
-
Educational Codeforces Round 86 (Rated for Div. 2)C. Yet Another Counting Problem
-
Educational Codeforces Round 48 (Rated for Div. 2) C. Vasya And The Mushrooms(思维)