前言
你要搞清楚自己人生的剧本不是你父母的续集，不是你子女的前传，更不是你朋友的外篇。
第三次考试，第二次被我咕掉了。
\(68+35+100=203\)，在高二没参考的情况下，\(\texttt{BZ Rk2}\)，也还算能看。
感觉这次的排名和上次是倒过来的。
T1 这么唐氏的 DP 状态有限，是可过的，居然被我直接否定掉了，我还是太愚蠢了。
T1
最开始只会 \(\mathcal{O}(2^n)\) 的位运算优化的爆搜，在一系列乱搞和剪枝下居然过掉了 \(n\le 30\) 的数据，这辈子也就只会乱搞了。
考虑一个更有优化前景的暴力 DP。即我们定义 \(dp_{i,S}\) 表示前 \(i\) 个数选的子序列集合为 \(S\)，对应的最大逆序对数和方案。复杂度应该是 \(\mathcal{O}(2^n\times n)\)。
但是显然，如果我们把所有的状态都记下来，显得有些冗余，因为有些对我们后面的逆序对影响不大。
假设 \(i\) 后面的数是 \(x_1,x_2,...x_k\)，（不妨设 \(x_1<x_2<....<x_k\)，其实我们只关心 \([1,x_1),(x_1,x_2),....(x_k,n]\) 在前 \(i\) 个中每段被选了多少个。于是状态数不会超过每段长度 \(+1\) 的乘积。
此时状态应该被减下去很多了，你写完之后发现可以通过。具体证明的话，可以使用柯西不等式，一定会在每段相同的时候取到状态数量的最大值，通过求导得到最值是 \(e^{\frac{n}{e}}\)，由于段长是整数，时间复杂度应该就是 \(3^{\frac{n}{3}}\times \text{poly}(n)\)。
可能使用 \(\text{map}\) 类的东西来暴力压状态会被卡常，可能需要实现精细一点。
貌似还有很多其他奇奇怪怪的做法（？
T2
感觉是一道挺不错的题，确实没想到这个地方可以使用分治来减小复杂度。
从 \(n=1,2,3\) 一个一个来。
先看 \(n=1\) 的时候，其实答案就是算每个点的贡献，即 \(2\times \sum_{i=1}^m \Big( a_i\times \big(i\times (m-i+1)-1\big)\Big)\)。
然后看 \(n=2\) 的时候怎么办。
发现一个性质，即从 \((x,y)\to (x',y')\) 的路径，假设 \(y \le y'\)，那么显然可以发现我们在路径中必然不存在从 \((a,b)\to (a,b-1)\) 这种向左走的情况。证明应该是显然的，因为是点权最短路。
考虑一个分治。对于分治区间 \([l,r]\)，我们统计所有 \(y\in [1,\text{mid}],y'\in [\text{mid}+1,r]\) 这样的所有 \((1,y)\to (1,y'),(1,y)\to (2,y'),(2,y)\to (1,y'),(2,y)\to (2,y')\) 这样的点对的答案。对于剩下的直接递归处理。
发现其实我们只需要关心 \(\text{mid}\) 这一列是怎么走到 \(\text{mid}+1\) 这一列去的。
考虑求出 \((1,\text{mid}),(2,\text{mid})\) 到列区间所有点的最短路。假设分别是 \(\text{dis}_{1,x,y}\) 和 \(\text{dis}_{2,x,y}\)。
对于 \((x,y)\to (x',y')\) 且要在当前递归中被计算的点对，发现当 \(\text{dis}_{1,x,y}+\text{dis}_{1,x',y'}< \text{dis}_{2,x,y}+\text{dis}_{2,x',y'}\) 时，从 \(\text{mid}\) 到 \(\text{mid}+1\) 列时，我们是从第一行走的，否则就是第二行。
我们将上述不等式化成如下形式：\(\text{dis}_{1,x,y}-\text{dis}_{2,x,y}< \text{dis}_{1,x',y'}-\text{dis}_{2,x',y'}\) ，应该在分治中就可以转化成一个一维偏序问题，对于从第一行和第二行分别统计答案即可。
时间复杂度 \(\mathcal{O}(m \log^2m)\)。
接下来看 \(n=3\) 怎么处理。
发现 \(n=3\) 是可能向左走的。但是发现从 \((x,y)\to (x',y')\) 且 \(y\le y'\) 的情况下，我们只有可能在起点处向左走若干步，中间一直向右，最后再向左走若干步到达终点。
这意味着什么呢，在递归区间中，\((x,y)\to (x',y')\) 可能经过的点不只是递归区间中的点，而是从左边走 \(\mathbf{U}\) 型拐进来的。
也就是说，我们只需要考虑从 \((1,y)/(3,y)\) 走到 \((3,y)/(1,y)\) 可能不是直接一列走下去，而是向左走一个 \(\mathbf{U}\) 型 或者向右走一个 \(\mathbf{U}\) 型。然后把这种 \(\mathbf{U}\) 型考虑到最短路求完之后。（因为为了保证复杂度，最短路不能经过递归区间外的点，就必须强行考虑 \(\mathbf{U}\) 这种走出区间的情况。）从 \(\forall i\in [1,m],(1,i)\to (3,i)\) 的情况都需要预处理，而且预处理应该是比较平凡的。
然后求出区间内所有的点到 \((1,\text{mid}),(2,\text{mid}),(3,\text{mid})\) 的最短路之后，刚才判断从 \(\text{mid}\) 到 \(\text{mid} +1\) 列是走的是哪一行就变成了 \(\text{dis}_{1,x,y}-\text{dis}_{2,x,y}< \text{dis}_{1,x',y'}-\text{dis}_{2,x',y'} \ \And \ \text{dis}_{1,x,y}-\text{dis}_{3,x,y}< \text{dis}_{1,x',y'}-\text{dis}_{3,x',y'}\) ，从而从一维偏序变成了二位偏序。然后由于你算的所有点对，这里的小于和小于等于的符号一定要想清楚，不然很容易算重。就你在从第一行和第二行过去都算到了同一个点对。
时间复杂度仍然是 \(\mathcal{O}(m\log^2m)\)。
代码非常恶心，长达 \(\texttt{10.4K}\)，仅供参考。
T3
以前做过，差点没想到决策单调性，险些没做出来。。。
首先有一个很显然的性质，对于所有重量为 \(i\) 的苹果，我们把这些苹果按照价格从大到小排序之后，如果重量为 \(i\) 的苹果被选择了 \(j\) 个，那么一定是选的苹果价值最大的 \(j\) 个。
于是我们考虑把 \(i=1,2,3,4,5\) 分别拎出来，每组苹果按照价值从大到小排序之后求一个前缀和。
然后考虑一个朴素背包 DP。定义 \(dp_{i,j}\) 表示考虑完重量为 \([1,i]\) 的所有苹果之后，当前运输了重量为 \(j\) 的苹果时，可以最多卖出多少价钱。
显然有转移 \(dp_{i,j}=\max _{k=0}^{\text{num}_i}dp_{i-1,j-k\times i}+\text{sum}_k\)，其中 \(\text{num}_i\) 表示重量为 \(i\) 的苹果有多少个，\(\text{sum}\) 数组是当前重量为 \(i\) 的苹果排序之后的价值前缀和数组。
发现 \((k,\text{sum}_k)\) 在排完序之后，所连成直线构成的图形应该是上凸的，这指向了决策单调。
发现 \(j\) 只会从 \(j'=j-k\times i\) 转移得到，也就是说 \(j'\equiv j\pmod i\)。
发现对于所有的 \(j\) 在模 \(i\) 的意义下分成 \(i\) 组，只有每组内部才可能产生转移，并且发现每个组内的转移由于 \((k,\text{sum}_k)\) 是上凸的，所有每组内的转移满足决策单调性。
然后直接整体二分维护决策单调即可，
时间复杂度 \(\mathcal{O}(c\times n\times \log (c\times n))\)。
标签：省选,text,复杂度,mid,times,Day10,苹果,模拟,dis From： https://www.cnblogs.com/SFsaltyfish/p/18654039