OJ题号：
BZOJ1863、CodeVS1513
思路：
当$n$为偶数时，可以将原数组按照出现的奇偶性分为两个集合，答案即为两个集合元素最大值之和。
当$n$为奇数时，二分答案，检验时进行动态规划，分别求出当前与$1$的最大冲突值$max$和最小冲突值$min$。 当$min_n=0$时，说明最小不会产生冲突，满足条件。 当$min_n≠0$时，说明在最优情况下同样会产生冲突，不满足条件。 另外需要注意二分时因为答案越小越优，因此当$check()$被满足时应该往小的二分，不然会WA。1 #include2 #include 3 #include 4 inline int getint() { 5 char ch; 6 while(!isdigit(ch=getchar())); 7 int x=ch^'0'; 8 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 9 return x;10 }11 const int N=20001;12 int n;13 int a[N],min[N],max[N];14 inline bool check(const int x) {15 min[1]=max[1]=a[1];16 for(int i=2;i<=n;i++) {17 min[i]=std::max(0,a[i]+a[i-1]+a[1]-max[i-1]-x);18 max[i]=std::min(a[i],a[1]-min[i-1]);19 }20 return !min[n];21 };22 int main() {23 n=getint();24 if(!(n&1)) {25 int max1=0,max2=0;26 for(int i=1;i<=n;i++) {27 if(i&1) {28 max1=std::max(max1,getint());29 }30 else {31 max2=std::max(max2,getint());32 }33 }34 printf("%d\n",max1+max2);35 return 0;36 }37 int tmp=0;38 for(int i=1;i<=n;i++) {39 a[i]=getint();40 tmp=std::max(tmp,a[i]+a[i-1]);41 }42 tmp=std::max(tmp,a[n]+a[1]);43 int l=tmp,r=tmp<<1;44 while(l<=r) {45 int mid=(l+r)>>1;46 if(check(mid)) {47 r=mid-1;48 }49 else {50 l=mid+1;51 }52 }53 printf("%d\n",l);54 return 0;55 }