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