描述

经过多年的杀戮，秦皇终于统一了中国。为了抵御外来的侵略，他准备在国土边境安置 n 名将军。

不幸的是这 n 名将军羽翼渐丰，开始展露他们的狼子野心了。他们拒绝述职、拒绝接受皇帝的圣旨。秦皇已经准备好了秘密处决这些无礼的边防大将。不过为 防兵变，他决定先授予这些将军一些勋章，为自己赢得战略时间。

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

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

输入

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

输出

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

样例输入[复制]

4

2

2

1

1

样例输出[复制]

4

标签

zjoi2006

 

 

这道题真的是神奇，惊呆了

如果n是偶数，显然直接贪心过去，相邻之间取最大值输出，这样可以得到60分（orz）

如果是奇数，那么就会出锅，因为最后相邻的两个人的勋章如果用之前的肯定是会出问题的

按照洛谷的题解，实质上就是每种勋章不能发给超过n/2个将军，然后直接除下就是答案了orz，但还是要跟贪心比一下取最大

神奇啊啊啊啊啊啊啊啊

这道题意义在于

横向思考每个勋章，贪心实际上是一种

纵向思考，考虑每个将军拥有的勋章个数，而这个是从每一枚勋章开始考虑，毕竟每个都是独一无二的（逃

code：

1 #include
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5 int a[20005]; 6 int main(){ 7     int n; 8     cin>>n; 9     int max0=0,min0=99999999;10     int sum=0;11     for(int i=1;i<=n;i++){12         cin>>a[i];13         sum+=a[i];14         min0=min(min0,a[i]);15         if(i>1)max0=max(max0,a[i]+a[i-1]);16     }17     max0=max(max0,a[n]+a[1]);18     if(n%2==0) 19     cout<