普及选手又来做省选题啦~~
注：作者只能帮助大家理解，有些地方可能不严谨，敬请谅解。
一、题目
传送门
二、解法
我们先考虑A不多吃的情况。
如果nnn为偶数，可以发现答案一定取max(a[mid],a[mid+1])\max(a[mid],a[mid+1])max(a[mid],a[mid+1])，为什么呢？考虑还有更大的a[i]a[i]a[i]在其他地方，那么B都可以通过他的n/2−1n/2-1n/2−1次机会取走，所以只有midmidmid和mid+1mid+1mid+1对于B来说是无能为力的，而A会根据a[mid],a[mid+1]a[mid],a[mid+1]a[mid],a[mid+1]的大小来决定先取哪一边。
如果nnn为奇数，可以发现答案为max(min(a[i],a[i−1]),min(a[i],a[i+1]))\max(\min(a[i],a[i-1]),\min(a[i],a[i+1]))max(min(a[i],a[i−1]),min(a[i],a[i+1]))，因为A先取之后问题就变成了B先取，从而变成了nnn为偶数的情况，A取哪边对应了两种min\minmin的取值，将他们取max\maxmax即可。
得到了A不多吃的情况，我们再考虑让A多吃的变化。
发现A多吃影响的是中间的取值，对于每一个被A吃过剩下的序列，我们找出它所有可能的中间点取值即可得到答案，这个过程考虑动态规划。
设ans[k]ans[k]ans[k]为剩下kkk个元素能取到的最大值，我们枚举i∈[1,n/2]i\in [1,n/2]i∈[1,n/2]，奇偶讨论，则有：
ans[2i]=max(ans[2i+2],dp1[i])ans[2i]=\max(ans[2i+2],dp1[i])ans[2i]=max(ans[2i+2],dp1[i])
ans[2i+1]=max(ans[2i+3],dp2[i])ans[2i+1]=\max(ans[2i+3],dp2[i])ans[2i+1]=max(ans[2i+3],dp2[i])
其中dp[1/0][i]dp[1/0][i]dp[1/0][i]表示中间点取iii的答案，要考虑到最左边和最右边为端点，dpdpdp将两种情况整合到了一起。
我们可以将这个方程理解为每次多增加一个中间点的取值，其他的取值继承上一个状态。
最后倒着输出ansansans，时间复杂度O(n)O(n)O(n)。
最后附上简洁却不简单的代码。
#include <cstdio>#include <iostream>using namespace std;const int MAXN = 300005;int n,a[MAXN],dp1[MAXN/2],dp2[MAXN/2],ans[MAXN];int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);ans[1]=max(ans[1],a[i]);}for(int i=1;i<n;i++)dp1[min(i,n-i)]=max(dp1[min(i,n-i)],max(a[i],a[i+1]));for(int i=2;i<n;i++)dp2[min(i-1,n-i)]=max(dp2[min(i-1,n-i)],max(min(a[i-1],a[i]),min(a[i],a[i+1])));for(int i=n/2;i>=1;i--){ans[i<<1]=max(ans[(i+1)<<1],dp1[i]);ans[i<<1|1]=max(ans[(i+1)<<1|1],dp2[i]);}for(int i=n;i>=1;i--)printf("%d ",ans[i]);}
