蓝桥杯算法提高-秘密行动 题解

解题思路:
我的想法比较笨，但是能对就好了啊。
注意事项:

参考代码:

#include<bits/stdc++.h>
#define rint register int
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
struct node{
	int x,y;
	int len;
	node(int a,int b,int c){
		x=a,y=b,len=c;
	}
};
int d[][2]={{-1,0},{1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+(c-'0');
		c=getchar();
	}
	return x*f;
}

//分割线---------------------------------------------- 
//正文部分： 
int n;
int a[N],dp[N];

int main()
{
	n=read();
	for(rint i=1;i<=n;i++)
		a[i]=read();
	
	dp[0]=0,dp[1]=a[1];
	//一定要走到n+1，因为n+1才是顶楼！！！ 
	for(rint i=2;i<=n+1;i++)//走两层时的最优解； 
	{
		//i-1：是不选择跳跃，而是选择连续跳的最优解
		//i-2：是选择从i-2跳跃到i的最优解
		//都加跳到这层楼的时间 
		dp[i]=min(dp[i-1],dp[i-2])+a[i];
	}	
	for(rint i=3;i<=n+1;i++)//走三层时的最优解； 
	{
		//i-1：是连续跳；
		//i-2：是跳两层
		//i-3：是跳三层  在这三种情况中选择一个最优解加上本层楼的时间；
		// 同时要与之前走两层到这i层的答案作比较，看是跳三层快，还是跳两层； 
		dp[i]=min(dp[i],min(min(dp[i-1],dp[i-2]),dp[i-3])+a[i]);
	}
	printf("%d\n",dp[n+1]);
	return 0; 
}