rnqoj-82-又上锁妖塔-dp

又是一个敢想就敢做的题目。。。

同时记录更新两个状态

dp[i] :第i层是飞上去的

df[i]  :第i层是走上去的

dp[i]=min(df[i-1],df[i-2]);

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

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int dp[10050];
int df[10050];
int main()
{int n,i;int a[10050];while(~scanf("%d",&n)){for(i=1;i<=n;i++)scanf("%d",&a[i]);df[1]=a[1];for(i=2;i<=n;i++){dp[i]=min(df[i-1],df[i-2]);df[i]=min(dp[i-1]+a[i],df[i-1]+a[i]);}cout<<min(dp[n],df[n])<<endl;}return 0;
}