试题 算法提高 秘密行动

蓝桥杯 算法提高 秘密行动 dp 总体思路是用dp[i][j] 状态是第i步能否可以跳跃 dp[i][1]是能够跳跃的，反之，dp[i][0]不能跳跃。 状态时

dp[i][1]=min(dp[i-1][1]+a[i],dp[i-1][0]+a[i]);
dp[i][0]=min(dp[i-1][1],dp[i-2][1]);

对应第一行时i-1步走上去， 第二行是没法跳跃，故前面是跳跃过了的。

#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
const int N =1e6+10;
int n,m;
struct cmp {
	bool operator()(const int&a,const int&b) const {
		return a>b;
	}
};
int dp[10010][2];
int a[10010];
int main() {
	cin >>n;
	for(int i =1;i<=n;i++)
	cin >> a[i];
	memset(dp,0,sizeof(dp));
	//dp[1][0]=a[0];
	//dp[1][0]=0;
	dp[1][1]=a[1];
	//dp[2][0]=0;
	for(int i =2;i<=n;i++){//1ÄÜÌø 
		dp[i][1]=min(dp[i-1][1]+a[i],dp[i-1][0]+a[i]);
		dp[i][0]=min(dp[i-1][1],dp[i-2][1]);		
	}
	cout<<min(dp[n][1],dp[n][0]);
	return 0;
}