题目名称	2016. [ZJOI 2006] 皇帝的烦恼
输入输出	`trouble2006.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	8
题目来源	于2015-10-25加入
开放分组	全部用户
提交状态
分类标签	贪心二分法动态规划
	分享题解

通过：82，提交：206，通过率：39.81%
灰里城	100	0.000 s	0.00 MiB	C++
槿柒	100	0.000 s	0.00 MiB	C++
白&夜	100	0.012 s	0.39 MiB	C++
哒哒哒哒哒！	100	0.013 s	4.13 MiB	C++
Hzoi_Queuer	100	0.014 s	0.52 MiB	C++
Sky_miner	100	0.014 s	1.26 MiB	C++
‎MistyEye	100	0.017 s	0.46 MiB	C++
svideo	100	0.018 s	1.46 MiB	C++
Yuri	100	0.019 s	0.36 MiB	C++
阿狸	100	0.019 s	0.39 MiB	C++

关于皇帝的烦恼的近10条评论(全部评论)
这东西在DP时不需要开数组，用一个滚动变量把一维数组滚了就行了。 _Itachi 2016-10-13 20:48 4楼
回复 @owl city : 你要的PASCAL 白夜<=>黑天 2016-10-13 18:00 3楼
有没有大神用pascal做啊？ owl city 2015-11-03 20:18 2楼
哦吼吼 Dissolute丶Tokgo 2015-11-03 17:44 1楼

2016. [ZJOI 2006] 皇帝的烦恼

★★★ 输入文件：trouble2006.in 输出文件：trouble2006.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

经过多年的杀戮，秦皇终于统一了中国。为了抵御外来的侵略，他准备在国土边境安置n名将军。不幸的是这n名将军羽翼渐丰，开始展露他们的狼子野心了。他们拒绝述职、拒绝接受皇帝的圣旨。

秦皇已经准备好了秘密处决这些无礼的边防大将。

不过为防兵变，他决定先授予这些将军一些勋章，为自己赢得战略时间。将军们听说他们即将被授予勋章都很开心，他们纷纷上书表示感谢。第i个将军要求得到ai枚不同颜色的勋章。但是这些将军都很傲气，如果两个相邻的将军拥有颜色相同的勋章他们就会认为皇帝不尊重他们，会立即造反（编号为i的将军和编号为i+1的将军相邻；因为他们驻扎的边境可以类似看成一个圆形，所以编号1和编号n的将军也相邻）。

皇帝不得不满足每个将军的要求，但对他们的飞扬跋扈感到很气愤。于是皇帝决定铸造尽量少种类的勋章来满足这些狂妄者的要求。请问他至少要铸造多少种颜色的勋章？

【输入格式】

第一行有一个整数n(1<=n<=20000)。接下来n行每行一个整数ai，表示第i个将军要求得到多少种勋章。(1<=ai<=100000)

【输出格式】

输出一个整数，即最少需要多少种勋章。

【样例输入】

4
2 2 1 1

【样例输出】

【来源】

ZJOI2006