2017年9月2日普级组T2 跳格子

2024-01-29 20:48
文章标签 2017 t2 格子 日普级

本文主要是介绍2017年9月2日普级组T2 跳格子,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

大家都说要劳逸结合,Ayumi, Mitsuhiko, Genta画完方格就出去运动啦!
他们来到了一片空地,画了N个连续的方格,每个方格上随机填上了一个数字,大家从第一个格子开始,每次可以向后跳不超过当前格子上的数的步数,大家开始就此比赛,看谁跳到最后一个格子的步数最少。
作为队长的Genta显然是想获得胜利的,所以他打电话给Conan求助,可是Conan在玩游戏,所以就向你求助了。

Input

输入第一行包含一个整数N,表示画的格子的个数。
第二行包含N整数,表示每个格子上的数。

Output

输出一行,表示跳的最少步数。

Sample Input
5
2 3 1 1 1

Sample Output
2

分析
这题是一道dp(非常水)
设f[i]表示从格子1到格子i的最少步数
得:f[i]:=min(f[i],f[j]+1);a[j]+j>=i;1<=j<=i-1;

程序:

var
n,i,j:longint;
a,f:array[0..6000]of longint;function min(x,y:longint):longint;
beginif x<y then exit(x) else exit(y);
end;beginassign(input,'jump.in');reset(input);assign(output,'jump.out');rewrite(output);readln(n);for i:=1 to n doread(a[i]);for i:=2 to n dof[i]:=maxlongint;f[1]:=0;for i:=2 to n dofor j:=1 to i-1 doif a[j]+j>=i then f[i]:=min(f[i],f[j]+1);write(f[n]);close(input);close(output);
end.

这篇关于2017年9月2日普级组T2 跳格子的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/658144

相关文章

2017 版本的 WebStorm 永久破解

1.  在IntelliJ官网中下载 最新版本的WebStorm   下载地址:https://www.jetbrains.com/webstorm/download/#section=windows 2. 获取注册码    获取地址:http://idea.lanyus.com/   点击获取注册码,然后将注册码复制,再打开最新版的WebStorm,将注册码粘贴到激活框中就大功告

网易2017秋招编程题集合--完全解析

前言 一些大公司的真题里面总有些含金量很高的几个题,网易2017秋招编程题集合里面也有几个题是非常好的,比如说第三题跳石板,第四题黑暗的字符串都是很好的题目。特别是第四题的那种思路之前几乎完全没有接触过,还有第六题最大的奇约数里面还有部分数学思维在里面。 1.回文序列 题目描述:如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如: {1, 2, 1}, {15, 7

Fastjson1.2.24(CVE-2017-18349)分析

前言 Fastjson在1.2.24版本之前存在两条利用链,分别是 JNDI com.sun.rowset.JdbcRowSetImplcom.sun.org.apache.xalan.internal.xsltc.trax.TemplatesImpl 我们本次也是对这两条链进行分析和过程复现 在fastjson漏洞中,我们往往是寻找一个类,它的构造函数、 getter,setter 方法有问

NLP-生成模型-2017-Transformer(一):Encoder-Decoder模型【非序列化;并行计算】【O(n²·d),n为序列长度,d为维度】【用正余弦函数进行“绝对位置函数式编码”】

《原始论文:Attention Is All You Need》 一、Transformer 概述 在2017年《Attention Is All You Need》论文里第一次提出Transformer之前,常用的序列模型都是基于卷积神经网络或者循环神经网络,表现最好的模型也是基于encoder- decoder框架的基础加上attention机制。 2018年10月,Google发出一篇

NLP-预训练模型-2017:ULMFiT(Universal LM Fine-tuning for Text Classification)【使用AWD-LSTM;模型没有创新;使用多个训练小技巧】

迁移学习在计算机视觉有很大的影响,但现在的NLP中的方法仍然需要特定任务的修改和 从头开始的训练。我们提出通用语言模型微调,一种可以应用NLP任何任务中的迁移学习方法。我们模型在分类任务中都表现得良好,并且在小数据集上的表现优异。 一、ULMFiT (Universal Language Model Fine- tuning)组成步骤: a) General-domain LM pretr

NLP-文本匹配-2017:BiMPM【Bilateral Multi-Perspective Matching for Natural Language Sentences】

NLP-文本匹配-2016:BiMPM【Bilateral Multi-Perspective Matching for Natural Language Sentences】

2017-择善而从

前言   此文是2017上半年对自己工作和生活的回顾总结,也是给自己一个停下脚步安静思考的机会。每个努力生活的人,老天都会待你不薄。勉励自己在新的日子里,努力生活,择善而从。 Coding-内外兼修   一直觉得中国的武术有着深厚的哲学思想,蕴含着事物的本质。传统中华武术注重内外兼修,既修内容,又练外功。编程也是一样,要内外兼修。不仅要学习层出不穷的“新技术”,更要去思考其本质,掌握

2017年华为精英挑战赛

http://blog.csdn.net/h532600610/article/details/70183608 http://blog.csdn.net/mmy1996/article/details/64443159

2017/05/17 java 基础 随笔

2017/05/17 java 基础 随笔   posted @ 2017-05-17 08:36 酸奶加绿茶 阅读( ...) 评论( ...) 编辑 收藏

2017/05/16 java 基础 随笔

2017/05/16 java 基础 随笔 1,成员变量和局部变量的区别   1)在内存中的位置不同     成员变量:在堆内存(成员变量属于对象,对象进堆内存)     局部变量:在栈内存(局部变量属于方法,方法进栈内存)   2)初始化值不同     成员变量:有默认初始化值     局部变量:没有默认初始化值,必须定义,赋值,然后才能调用。 2.封装   private:被修饰的