二分答案，dp 检验
dp 不是很好想
f 记录与第一个位置相同个数的最大值
g 记录与第一个位置相同个数的最小值1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
const int N=20050;
int n,maxs,sum=0,w[N],f[N],g[N];//f>>max g>>min
bool check(int k)
{
f[1]=g[1]=w[1];
for(int i=2;i<=n;i++)
{
f[i]=min(w[1]-g[i-1],w[i]);
g[i]=max(0,w[i]-(k-w[i-1]-w[1]+f[i-1]));
}
return !g[n];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&w[i]),sum+=w[i];
maxs=w[1]+w[n];
for(int i=1;i<n;i++) maxs=max(maxs,w[i]+w[i+1]);
if (!(n&1)) {printf("%d",maxs);return 0;}
int L=maxs,R=sum;
while (L<R)
{
int mid=(L+R)>>1;
if (check(mid))
R=mid;
else
L=mid+1;
}
printf("%d",L);
return 0;
}