魔法少女【动态规划问题】——NYOJ1204

个人博客页:https://www.scriptboy.cn/202.html

题目描述:

前些时间虚渊玄的巨献小圆着实火了一把。 在黑长直(小炎)往上爬楼去对抗魔女之夜时,她遇到了一个问题想请你帮忙。 因为魔女之夜是悬浮在半空的,所以她必须要爬楼,而那座废墟一共有n层,而且每层高度不同,这造成小炎爬每层的时间也不同。不过当然,小炎会时间魔法,可以瞬间飞过一层或者两层[即不耗时]。但每次瞬移的时候她都必须要至少往上再爬一层(在这个当儿补充魔力)才能再次使用瞬移。爬每单位高度需要消耗小炎1秒时间。 消灭魔女之夜是刻不容缓的,所以小炎想找你帮她找出一种最短时间方案能通往楼顶。

输入描述:

本题有多组数据,以文件输入结尾结束。 每组数据第一行一个数字N(1 <= N <= 10000),代表楼层数量。 接下去N行,每行一个数字H(1 <= H <= 100),代表本层的高度。

输出描述:

对于每组数据,输出一行,一个数字S,代表通往楼顶所需的最短时间。

样例输入:

5 3 5 1 8 4

样例输出:

1

思路:

假设h[n+1]表示每层的高度,h[0]=0,f[i][0]表示在第i层不飞情况下的时间,f[i][1]表示在第i层飞的情况下的时间,可见有如下关系:

  1. 如果层数i=1,如果在不飞的情况下,f[1][0] = h[1];在飞的情况下,f[1][1] = 0;
  2. 如果层数i=2,如果在不飞的情况下,f[2][0] = h[2];在飞的情况下,f[1][1] = 0;
  3. 如果层数i=3,如果在不飞的情况下,f[3][0] = min(f[2][0], f[2][1])+h[3];在飞的情况下(可以是飞一层到i层,也可以是飞),f[3][1] = min(f[2][0], f[1][0]);
  4. 所以可以看出,状态转移方程为f[i][0] = min(f[i-1][0], f[i-1][1])+h[i]f[i][1] = min(f[i-1][0], f[i-2][0])

AC代码:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

#include <bits/stdc++.h> using namespace std; int f[10005][2]; int h[10005];   int main() {     int n;     while(cin >> n)     {         for(int i = 1; i <= n; i++)         {             cin >> h[i];         }         f[1][0] = h[1];f[1][1] = 0;         f[2][0] = h[2];f[2][1] = 0;         for(int i = 3; i <= n; i++)         {             f[i][0] = min(f[i-1][0], f[i-1][1]) + h[i];             f[i][1] = min(f[i-1][0], f[i-2][0]);         }         cout << min(f[n][0], f[n][1]) << endl;     }     return 0; }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏简书专栏

基于jieba、gensim.word2vec、LogisticRegression的文档分类

建议读者安装anaconda,这个集成开发环境自带了很多包。 到2018年8月30日仍为最新版本的anaconda下载链接: https://pan.baid...

37940
来自专栏PaddlePaddle

PaddlePaddle发布新版API,简化深度学习编程

PaddlePaddle是百度于2016年9月开源的一款分布式深度学习平台,为百度内部多项产品提供深度学习算法支持。为了使PaddlePaddle更加易用,我们...

35880
来自专栏H2Cloud

A星路径搜索

摘要:   在人工智能中有一类问题是有确定解的,如路径、五子棋等,这样的问题非常适合使用搜索来解决。 路径搜索是一个很有趣的问题,在人工智能中算是很基础的问题。...

55540
来自专栏磐创AI技术团队的专栏

Tensorflow 免费中文视频教程,开源代码,免费书籍.

Free-Tensorflow Tensorflow 免费中文视频教程,开源代码,免费书籍. ? 官方教程 官方介绍 https://tensorflow.go...

41860
来自专栏人工智能的秘密

用机器学习来预测天气Part 1

  本章是使用机器学习预测天气系列教程的第一部分,使用Python和机器学习来构建模型,根据从Weather Underground收集的数据来预测天气温度。该...

43090
来自专栏机器之心

教程 | 如何用百度深度学习框架PaddlePaddle做数据预处理

34960
来自专栏AI科技评论

实战 | BERT fine-tune 终极实践教程

AI科技评论按:从 11 月初开始,google-research 就陆续开源了 BERT 的各个版本。google 此次开源的 BERT 是通过 tensor...

70550
来自专栏机器学习算法工程师

史上最详细的XGBoost实战(上)

作者:章华燕 编辑:祝鑫泉 零 环境介绍: · Python版本:3.6.2 · 操作系统:Windows · 集成开发环境:PyCharm 一 安装Pyt...

71840
来自专栏北京马哥教育

搭建python机器学习环境以及一个机器学习例子

作者 | hzyido 来源 | 简书 糖豆贴心提醒,本文阅读时间6分钟,文末有秘密! 这篇文章介绍了Python机器学习环境的搭建,我用的机器学习开...

611120
来自专栏青青天空树

取随机数

  常用于去随机数的函数为rand()(在stdlib.h头文件中,不同的编译器可能有不同),但是实际在使用这个函数时却发现每次程序运行产生的数都是一样的,这是...

17120

扫码关注云+社区

领取腾讯云代金券