[问题描述]
有一个环形的围墙，围墙上有一些塔，每个塔中有一个守卫。现在要发给每个守卫一些奖章，第i个守卫需要P[i]个奖章。每个守卫自己的奖章必须都是不同种类的，而且相邻的两个守卫得到的奖章也不能有任何一个相同。问至少应准备多少种不同的奖章。（限制：2≤n≤10000，1≤P[i]≤100000）
[分析]
假如围墙不是环形的，我们很容易用贪心算法解决：每次发给守卫尽可能多的已准备的奖章，如果不够就再新准备若干种以满足需要。但现在围墙是环形的，最后一个守卫与第一个守卫也不能有重复的奖章，这就是问题的难点。
于是我们尝试将这一难点引入状态，用动态规划求解（动态规划是求解最优性问题的一种常用方法）。
令a[i,j]表示前i个守卫已安排妥当，且第i个守卫有j个奖章与第一个守卫相同，则除第一个守卫已有的P[1]种奖章外，至少还需要的奖章种数。
如图，假设第i-1个守卫有k个奖章与第一个守卫相同，由于这k个奖章与第i个守卫的j个奖章必须互不相同，易知j+k≤P[1]；又由于第i-1个守卫的另外P[i-1]-k个奖章必须与第i个守卫的另外P[i]-j个奖章不同，设需要增加X种奖章，则
a[i-1,k]+X ≥ (P[i]-j)+(P[i-1]-k)
得到X ≥ (P[i]-j)+(P[i-1]-k) - a[i-1,k]
于是我们有
显然就这样做复杂度高达O(n*Pmax2)。即使使用了优化，也很难得到令人满意的结果，我们只得另辟蹊径。
考虑到如果有P[1]+X种奖章，存在一种分发方案满足要求，那么如果我们有P[1]+X+1种奖章，也一定存在可行方案（大不了其中一种我们不用）。这个性质非常重要，因为由此，我们可以就用二分枚举X，再逐个判断是否有可行方案的方法求得结果。
所以原先问题就转化为——如果我们已经知道共有P[1]+X种奖章，我们能否很快判断是否存在满足要求的分发方案呢？答案是肯定的。
方法仍旧是动态规划[1]，状态表示也类似，a[i,j]表示共有P[1]+X种奖章，前i个守卫已安排妥当，且第i个守卫有j个奖章与第一个守卫相同是否可能。
则状态转移变为：
表面上看状态转移仍旧很繁琐，k的取值有很多限制。但我们仔细观察，第二、三条合起来是P[i-1]+P[i]-X-j ≤ k ≤ P[1]-j。
对于确定的i，k的取值范围在数轴上的表示是一条长度确定的线段，且线段的位置由j确定。原先第一条限制只不过是再给线段限定一个范围，去除多余无意义的部分（如图）。
初始状态a[1]中只有a[1,0]=true，其余均为false。由归纳法很容易证明对任意i，a[i,j]中为true的j一定是连续的一段。由此对每个i，所有状态a[i,j]可仅用两个端点表示，即a[i].x1、a[i].x2。
考虑要使a[i,j]=true，当且仅当k的取值范围与线段[a[i-1].x1,a[i-1].x2]有交集，即满足
P[1]-j ≥ a[i-1].x1 and P[i-1]+P[i]-X-j
≤ a[i-1].x2
即 P[i-1]+P[i]-X-a[i-1].x2 ≤ j ≤ P[1]-a[i-1].x2
由此，状态转移方程变为：
a[i].x1=max( 0 ,
P[i-1]+P[i]-X-a[i-1].x2 )
a[i].x2=min( P[i] ,
P[1]-a[i-1].x1 )
初始状态a[1].x1=a[1].x2=P[1]，状态总数O(n)，状态转移O(1)，可以说是高效的。
有了此方法，鉴于先前的分析，我们采用二分枚举X，并利用高效的测试方法，即可在O(n*logPmax)的时间解决整个问题。
[小结]
上面这个问题，看似难点仍旧在于动态规划，二分枚举只不过充当了一个附加手段。但实际上事先枚举的X，极大地简便了动态规划的方程，才使得问题得以解决。应用这类二分枚举思想的最优性问题近来很是热门，而且这类试题很容易诱导选手直接采用动态规划或是贪心算法，而走入死胡同。
所以，今后我们在考虑最优性问题时，应注意问题是否隐含了一个有序的01序列，它是否可以用二分枚举的方法将最优性问题转化为可行性问题。切记！“退一步海阔天空”。