noip2013提高组复赛试题day2

《noip2013提高组复赛试题day2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国信息学奥林匹克联赛（NOIP2013）复赛提高组day2CCF全国信息学奥林匹克联赛（NOIP2013）复赛提高组day2（请选手务必仔细阅读本页内容）一．题目概况中文题目名称积木大赛花匠华容道英文题目与子目录名blockflowerpuzzle可执行文件名blockflowerpuzzle输入文件名block.inflower.inpuzzle.in输出文件名block.outflower.outpuzzle.out每个测试点时限1秒1秒1秒测试点数目101020每个测试点分值10105附加样例文件有有有结果比较方式全文比较（过滤行

2、末空格及文末回车）题目类型传统传统传统运行内存上限128M128M128M二．提交源程序文件名对于C++语言block.cppflower.cpppuzzle.cpp对于C语言block.cflower.cpuzzle.c对于pascal语言block.pasflower.paspuzzle.pas三．编译命令（不包含任何优化开关）对于C++语言g++-oblockblock.cpp-lmg++-oflowerflower.cpp–lmg++-opuzzlepuzzle.cpp-lm对于C语言gcc-oblockblock.c-lmgcc

3、-oflowerflower.c–lmgcc-opuzzlepuzzle.c-lm对于pascal语言fpcblock.pasfpcflower.pasfpcpuzzle.pas注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3、全国统一评测时采用的机器配置为：CPUAMDAthlon(tm)64x2DualCoreCPU5200+，2.71GHz，内存2G，上述时限以此配置为准。4、只提供Linux格式附加样例文件。5、特别提醒：评

4、测在NOILinux下进行。第5页共5页全国信息学奥林匹克联赛（NOIP2013）复赛提高组day21．积木大赛(block.cpp/c/pas)【题目描述】春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是ℎi。在搭建开始之前，没有任何积木（可以看成块高度为0的积木）。接下来每次操作，小朋友们可以选择一段连续区间[L,R]，然后将第L块到第R块之间（含第L块和第R块）所有积木的高度分别增加1。小M是个聪明的小朋友，她很快想出了建造大厦的最佳策略

5、，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。【输入】输入文件为block.in输入包含两行，第一行包含一个整数n，表示大厦的宽度。第二行包含n个整数，第i个整数为ℎi。【输出】输出文件为block.out仅一行，即建造所需的最少操作数。【输入输出样例】block.inblock.out5234125【样例解释】其中一种可行的最佳方案，依次选择[1,5][1,3][2,3][3,3][5,5]【数据范围】对于30%的数据，有1≤n≤10；对于70%的数据，有1≤n≤1000；对

6、于100%的数据，有1≤n≤100000，0≤hi≤10000。2．花匠(flower.cpp/c/pas)【问题描述】花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。具体而言，栋栋的花的高度可以看成一列整数ℎ1,ℎ2,…,ℎn。设当一部分花被移走后，剩下的花的高度依次为g1,g2,…,gm，则栋栋希望下面两个条件中至少有一个满足：条件A：对于所有的1≤i≤，有g2i>g2i-1，同时对于所有的1≤i≤，有

7、g2i>g2i+1；第5页共5页全国信息学奥林匹克联赛（NOIP2013）复赛提高组day2条件B：对于所有的1≤i≤，有g2i1时最多有一个能满足。请问，栋栋最多能将多少株花留在原地。【输入】输入文件为flower.in。输入的第一行包含一个整数，表示开始时花的株数。第二行包含个整数，依次为ℎ1,ℎ2,…,ℎn，表示每株花的高度。【输出】输出文件为flower.out。输出一行，包含一个整数，表示最多能留在原地的花的株数。【输入输出样例

8、】flower.inflower.out5532123【输入输出样例说明】有多种方法可以正好保留3株花，例如，留下第1、4、5株，高度分别为5、1、2，满足条件B。【数据范围】对于20%的数据