【2018寒假集训 Day2】【动态规划】又上锁妖塔
又上锁妖塔
(tower.in/tower.out)
[题目描述]
小D在X星买完了想要的东西,在飞往下一个目的地的途中,正无聊的他转头看了看身边的小A,发现小A正在玩<仙剑>,可是小A很奇怪,他一直在锁妖塔的周围转来转去,可是就是不进去,于是小D问他:“你在干什么?怎么不上去?”小A说:“我在想怎么从锁妖塔外面爬上去”(倒…) 锁妖塔的建造很特别,塔总共有n层,但是高度却不相同,这造成了小A爬过每层的时间也不同。小A会用仙术,每用一次可以让他向上跳一层或两层,但是每次跳跃后小A都将用完灵力,必须爬过至少一层才能再次跳跃(你可以认为小A需要跳两次一层才休息),小A想用最短的时间爬到塔顶,可是他不能找到时间最短的方案,所以请你帮他找到一个时间最短的方案让他爬到塔顶,小A只关心时间,所以你只要告诉他最短时间是多少就可以了。你可以最后跳到塔外即超过塔高。
[输入格式]
第一行一个数n (n<=10000),表示塔的层数。
接下来的n行每行一个数(<=100),表示从下往上每层的高度。
[输出格式]
一个数,表示最短时间
[样例输入]
5
3
5
1
8
4
[样例输出]
1
[数据规模]
对20%的数据,n<=10
对40%的数据,n<=100
对60%的数据,n<=5000
对100%的数据,n<=10000
【解题思路】
每一层都有两种走法,用仙术,或者爬。而每一层都可以上一层,或者上两层来。
而每次用完仙术,都必须休息一层的时间,所以需要两个一维数组来做动态规划,一个为上次用了仙术的最优值,一个为上次没有用仙术的最优值。
每次做的选择是用或者不用仙术。
以此可以写出状态转移方程
f[i][1]=min(f[i-1][2]+time[i],f[i-1][1]+time[i]);//两个选择,要么上次用了仙术,或者没用,这个存储没有用仙术的方法
f[i][2]=min(f[i-1][1],f[i-2][1]);//这个存储使用仙术的方法。
【参考程序】
#include<iostream>
#include<cstdio>
using namespace std;
int n,time[10005],f[10005][3];
int main()
{
freopen("tower.in","r",stdin);
freopen("tower.out","w",stdout);
cin>>n;
for (int i=1;i<=n;i++) cin>>time[i];
for (int i=1;i<=n;i++) memset(f[i],63,sizeof(f[i]));//初始化
f[1][1]=time[1];
f[1][2]=0;
for (int i=2;i<=n;i++)
{
f[i][1]=min(f[i-1][2]+time[i],f[i-1][1]+time[i]);
f[i][2]=min(f[i-1][1],f[i-2][1]);
}
int ans=min(f[n][1],f[n][2]);
cout<<ans;
return 0;
}
最新文章
- bzoj 1305 dance跳舞
- js拖动层原形版
- Java Web学习系列——Maven Web项目中集成使用Spring
- 这题实在不知道起啥名好了 分类: sdutOJ 2015-06-22 17:17 19人阅读 评论(0) 收藏
- 【转】Redis主从复制简介
- LINUX TOP,不是这样玩地!!!
- ASP.NET程序代码优化的七个方面
- ros消息时间同步与回调
- Shuttle ESB 实践
- JavaScript-RegExp对象仅仅能使用一次
- JS中的数据类型和转换
- TCP的定时器系列 — 保活定时器
- PHP-MySQL基本操作
- 对nginx中location的认识
- JXL读取Excel(只支持xls版本)——(二)
- Robot FrameWork使用中常见问题收集
- mySQL内存及虚拟内存优化设置[转]
- CC2540 低功耗串口, POWER_SAVING 模式 下 串口 0 的使用
- linux+win7双系统重装win7修复grub的办法
- python 基础 8.4 re的 spilt() findall() finditer() 方法