题解 P2800 【又上锁妖塔】
曦行夜落
2018-01-26 16:03:33
我来提供一个不同的思路：
首先，这题可以这样表示状态——
f[i]表示爬到第i层的最少消耗，
dp[i]表示跳到第i层的最少消耗（注意，这里的爬和跳都是针对上一次来说的）
那么第一次，跳肯定不花费，爬要花费
所以，f[0]=0 f[1]=a[1] dp[0]=dp[1]=0
然后，由于跳过就不能再跳了，所以数组dp的转移方程如下：
dp[i]=min(f[i-1],f[i-2]) 也就是要么从前一层，要么前两层跳来，而且跳之前的那一次必定是爬
那么f的转移也呼之欲出了
f[i]=min(f[i-1],dp[i-1])+a[i]也就是从前一层爬来，那么到达前一层有两种方式：跳或者爬，不管怎样，都要加上花费
然后，边界和方程都有了，编程就简单了
附上代码
```c++
#define maxn 10000+50
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a[maxn],f[maxn],dp[maxn];
int main()
{
int n;
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
f[0]=0; dp[0]=0;
f[1]=a[1]; dp[1]=0;
for (int i=1;i<=n;++i)
{
f[i]=min(f[i-1],dp[i-1])+a[i];
dp[i]=min(f[i-1],f[i-2]);
}
printf("%d",min(f[n],dp[n]));
return 0;
}
```