题目描述

输入格式

输出格式

输入输出样例

4
2 2 1 1

一句话题意：

• 有N个将军，每人想要一定量的勋章，他们排成一个环，每个人和他相邻的两个人有的勋章都不能一样，问总共要造多少个勋章

考试时没时间时骗分的方法

• 这题第一眼会产生两种方法：一个事二分加乱搞，另一个就是贪心+撞运气，在完全没有思路或者没时间的时候第二种方法加一个对拍就是一个好的方法；
• 这题感觉考试时不少人都在贪，廖半仙和ZWJDD不知道咋搞的炸了，可为啥我的贪心没有脑子，还有55分？？？
• 感觉凭感觉会觉得答案就是A[i]+A[i+1]的最大值，至于为什么证明后面会有。
• 然后交上去，也确实啥也没判，也没分奇偶，还有分，还怪多。。。

考试时在时间很多/第三题一点也不会时（就像这次）搞的正解

• 正解感觉也很神奇，对于考试时是怎么想到的，我也不知道，感觉什么都不能用，那就DP吧。。。
• 先举几个栗子：

样例：巨水，偶数个，很简单可得有四个                              5个人，没人都要一个，可得要三个                     三个人，每人要一个，共要3个

• 一个大胆的想法偶数时，很简单，自己和相邻的一个人取一个最大值，因为是偶数个，可以将奇数分为一组，偶数分为一组，让他们没有勋章是一样的，很容易可以想到。
• 在看后面两个奇数时，发现没有什么明显的规律，那就很明显的发现，这题难就难在奇数，任何奇数都可以拆成2*N+1的形式，那最后的那个1怎么办？

奇数时判断的方法（重点）：

• 重点就在于怎么判断最后一个和第一个（废话。。。）
• 这题贪心果断排除，什么其他高级算法也想不到，那就写DP吧。。。感觉除了长得清奇一点还是很好想的。
• maxn【i】：表示在前（i-1）个均不冲突时，第i个点与第1个点冲突的最大值
• mx【i】：表示在前（i-1）个均不冲突时，第i个点与第1个点冲突的最小值
• 方程式1：maxn【i】=min ( a [ i ]  , a [ 1 ]  -  mx [  i-1  ]  )
• 解释：要使  i  和  1  的冲突最大，而且还不能让  i  和  i-1  的冲突太大，那就表明  i-1  和  1  的冲突要尽可能的小，而  A[1]  中除去   mx[i-1]   之后，剩下的所有元素都合适，故得证。
• 方程式2：mx[  i  ]=max (  0  ,   a  [  i  ]  --  (  x  -  a  [  i  -  1  ]  -  a  [  i  ]  +  maxn  [  i-1  ]));
• 解释：要想使冲突最小，那就意味着除去不得不冲突的，其他一定不冲突。。。设总共有X种不同的勋章（这个事二分出来的） ，a  [  i  ]  --  (  x  -  a  [  i  -  1  ]  -  a  [  i  ]  +  maxn  [  i-1  ]  )表示在X种中除去必须和  1  还有  i-1  冲突的，由于可能有重复，所以还要加上maxn  [  i-1  ]  （此时可令  1 和  i-1的冲突很大，这样可以保证剩下来的最多。）如果剩下的额不足 A[ i ]  则表示一定会冲突。
• 判断：最后判断一下mx【N】是否为0，如果为0就意味着当前的X是成立的。
• 最后就是代码

NOIP模拟赛18 皇帝的烦恼O(∩_∩)O 二分+DP

原文：https://www.cnblogs.com/2529102757ab/p/11570001.html