跳跃的蚂蟥
一栋大楼高n层，第i层的高度为hi，一只蚱蜢从大楼外面的地面开始向上跳跃，无论每一层的高度是多少，蚱蜢都可以一次跳1层或2层，但是蚱蜢不能连着跳2次，所以每次跳跃之后接下来蚱蜢都至少要爬一层后才能再次跳跃，跳跃是不花时间的，但是攀爬是需要耗费时间的，具体耗费的时间值等于蚱蜢爬过的这一层或多层的高度。蚱蜢有时候跳跃有时候攀爬直到到达建筑物的楼顶为止。那么蚱蜢最快需要多久能够到达楼顶。
输入
输入第1行一个整数n。
输入第2行一共n个整数，第i个整数hi表示第i层的高度。
输出
输出一个整数，表示蚱蜢跳到楼顶需要耗费的最小时间。
样例输入 Copy
5 3 5 1 8 4
样例输出 Copy
1
提示
样例2解释：
先跳跃第1层，然后爬第2层，第2层高度为2，所以蚱蜢需要耗费的时间为2；
然后蚱蜢继续跳跃3,4两层，接着爬第5层，第5层高度为3，所以耗费时间为3；
然后蚱蜢跳跃第6层，此时到达楼顶。
所以总耗费时间就是2+3=5
1<=n<=10^6
1<=hi<=100
#include<bits/stdc++.h>
using namespace std;
int f[1000005][2],a[1000005];
int n;
int main ()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
f[i][0]=min(f[i-1][1],f[i-1][0])+a[i];
if(i>=2)
{
f[i][1]=min(f[i-1][0],f[i-2][0]);
}
}
int res=min(f[n][0],f[n][1]);
printf("%d",res);
return 0;
}
原文地址：https://blog.csdn.net/wsdsbtzk/article/details/142797289
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！