若数学公式无法显现请自行刷新




非常具有技巧性的一题

首先转化题意，由于选了以后会融合放回去，就相当于数还在。那么选择第i个，得到的分数就是前缀和$S[i]$.

考虑DP，正着推,找不到突破口…

发现不管是谁，最后一次得到的分数都是$s[n]$,因此考虑逆推.

假设先手全选了，那么最大差值 $MAX$ = $s[n]$

如果是先手选一次,后手选一次,先手选在m点(m<n)，（后手只能选在n点了）且最大差值更大

那么根据定义得 $s[m]-s[n] > MAX$ (MAX=s[n])

如果先手选两次，后手选一次,选择顺序是 k,m,n (k<m) ,且最大差值更大

那么根据定义得 $s[k]-s[m]+s[n] > MAX$ (MAX=s[m]-s[n])

加个括号 $s[k]-(s[m]-s[n]) > MAX$

发现了什么？ 如果从n点逆推回去,那么就有$MAX=max(MAX,s[i]-MAX)$;

至此得递（逆？）推式

OVER