题解 CF1372D 【Omkar and Circle】

题意：有一个$n$个元素的环$a$，一次操作可以把子串$\{a_x,a_{x+1},a_{x+2}\}$变成$\{a_x+a_{x+2}\}$。要求最后剩下的元素最大。 --- 首先我想到了一个贪心，使用堆维护，每次把最小的删了，变成旁边两个的和。结果就假了，WA on pretest 5。然后我对拍了一下，Hack数据： ```plain 5 9 4 2 3 7 ``` 这样我就会首先贪$2$,变成$\{9,7,7\}$，然后贪$7$，变成$\{16\}$。然而最优解会先选$3$，变成$\{9,4,9\}$，然后选$4$，变成$\{18\}$。思考一下，可以发现错误的根本在于选了$2$之后，**其相邻的数就不能选了**，只能舍近求远去选$7$。所以这个贪心是假的。 试图修锅，我发现选择一个数之后，相邻的数就不能再被选到，并且其他数的选择仍然是自由的。答案就是所有元素之和扣除掉选择的数的贡献。这样子就可以把原题面转化成下面的问题: > 有一个$n$个元素的环$a$，要求从中选出$k$个不相邻的元素，使其总和最小。 其中的$k=\dfrac{n-1}2$。不难写出一个$O(n^2)$的DP，$f_{i,j,0/1,0/1}$表示破环成链之后，前$i$个元素中选了$j$个，第一个元素选了/没选，第$i$个元素选了/没选的最优解。答案就是$\max{\{f_{n,k,0,0},f_{n,k,1,0},f_{n,k,0,1}\}}$。 考虑优化这个DP。可以发现$f_{i,j,x,y}-f_{i,j-1,x,y}\le f_{i,j+1,x,y}-f_{i,j,x,y}$，所以直接上带权二分，让每选择一个元素都要附加$w$的贡献。 有一个代码细节：这里的$w$的下界不能只开到$-10^9-10$这种级别的数，否则会WA on pretest 6。我也不知道这是为什么（感觉上够了啊?）但是把下界开更小一点就AC了。 代码： ```cpp #include<bits/stdc++.h> using namespace std; using ll=long long; int n;ll a[1<<18],tot; struct st{ll f;int c;}f[1<<18][2][2]; bool operator<(st a,st b){return a.f<b.f || a.f==b.f && a.c<b.c;} st chk(ll w){ for(int i=1;i<=n;i++) f[i][0][0].f=f[i][0][1].f=f[i][1][0].f=f[i][1][1].f=4e18; f[1][0][0]={0,0},f[1][1][1]={a[1]+w,1}; for(int i=2;i<=n;i++)for(int j:{0,1}){ f[i][j][0]=min(f[i-1][j][0],f[i-1][j][1]); f[i][j][1]={f[i-1][j][0].f+a[i]+w,f[i-1][j][0].c+1}; } return min({f[n][1][0],f[n][0][0],f[n][0][1]}); } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",a+i),tot+=a[i]; ll l=-2e12-10,r=10,mid; while(l<r){ mid=l+r>>1; if(chk(mid).c>(n-1)/2)l=mid+1;else r=mid; } st x=chk(l); printf("%lld\n",tot-(x.f-x.c*l)); return 0; } ```