上章回顾：Link

题目计数：\(151\)。

完了，刷不动题了/kk。

\(151.\) P4409 [ZJOI2006]皇帝的烦恼

有关集合关系的 dp 题，感觉好神仙，qwq。

还要二分，时间复杂度是 \(\mathcal O(n\log n)\)。

#include"iostream"
#include"cstdio"
#include"cmath"
using namespace std;

#define MAXN 20005
#define read(x) scanf("%d",&x)

int n,a[MAXN];
int minx[MAXN],maxn[MAXN];
int l,r;

int check(int x)
{
	for(int i=2;i<=n;i++)
	{
		minx[i]=max(0,a[i]-(x-(a[1]+a[i-1]-maxn[i-1])));
		maxn[i]=min(a[i],a[1]-minx[i-1]);
	}
	return minx[n]?0:1;
}

int main()
{
	read(n);
	for(int i=1;i<=n;i++) read(a[i]);
	a[0]=a[1];
	for(int i=0;i<n;i++) l=max(l,a[i]+a[i+1]);
	r=2*l,minx[1]=maxn[1]=a[1];
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}