CF1239E Turtle

给定 \(2\times n\) 的棋盘，要求重新安排布局，使得所有从 \((1,1)\) 走到 \((2,n)\) 的路径中最大点权和最小。 \(n\leq25,a_i\leq5\times10^4\) 。

首先确定每一条路径都是 \((1,1)\rightarrow(1,i)\rightarrow(2,i)\rightarrow(2,n)\) ，那么一个显然的贪心策略就是安排第一排单调递增，第二排单调递减。又因为 \((1,1)\) 和 \((2,n)\) 作为必然会经过的 \(2\) 个点，所以挑选最小的两个 \(a_i\) 一定最优。

考虑剩下的 \(2\times(n-1)\) 个点，设 \(a_2\leq a_3\leq a_4\leq\cdots\leq a_n\) ， \(b_1\geq b_2\geq b_3\geq\cdots\geq b_{n-1}\) ，表示第 \(1\) 行和第 \(2\) 行的数。依次考虑枚举中转点 \(i\) 。则答案的增量 \(\Delta=a_i-b_{i-1}\) ，由于 \(a_i\) 递增， \(b_i\) 递减， \(\Delta\) 将递增。即，答案的差值递增，答案为单谷函数。所以当 \(i\) 取到 \(1\) 或 \(n\) 时最大。

那么答案就变成了求 \(\max(\sum\limits_{i=2}^{n}a_i,\sum\limits_{i=1}^{n-1}b_i)+a_1+b_n\) 。即，需要求剩下 \(2\times(n-1)\) 个数取 \(n-1\) 个数这 \(n-1\) 个数的和尽可能接近这 \(2\times(n-1)\) 个数的和的一半。那么由于值域不大，可以使用背包的方法在 \(n^2\sum a_i=n^3a_i\) 的复杂度内完成：设 \(f[i][j][k]\) 表示前 \(i\) 个点中取 \(j\) 个使得其和为 \(k\) 是否可能。则 \(f[i][j][k]=f[i-1][j][k]\oplus f[i-1][j-1][k-a_i]\) 。

同时背包的过程可用 bitset 优化，最终复杂度为 \(O(\frac{n^2\sum a_i}{w})\) 。