1.当序列为已排序状态.则无论怎么操作都是有序的.
因此答案就是判断原序列是否非降序即可.
通过观察可以发现每次分隔的时候将每一个数自己构成一个区间就是最优的.
因此只需要计算每一个数对于$ans$的贡献是多少然后累加即可.
1.首先手写下样例可以发现无论中间构成是什么样的基本上都可以实现操作
2.因此只需要考虑特殊的不能实现的样例即可
分别是全1的:这样每一个数都不能帮助其他的数.
或 长度为3,且中间是奇数:这样中间的数也无法被其他数帮助到.
首先肯定化简式子,暴力来莽肯定不行$2^{100}$显然是不行的
解释下为什么要化简,尝试了一下不化简硬莽,发现有大问题。
最开始想用状态机 直接记录是否 交换。交换的话回传一下影响就行了。
但发现第i次决策的时候完全是无法确定其交换后的影响应该回传给谁。
因为每次决策是有后效性的。因此不拆分式子用状态机显然是不行的
以$a$数组为例,由于$a,b$数组式子是一样的化简一个就行了.
化简完合并下$a,b$两个式子.放在一起观察$ans$
这里很明显的可以发现除去前缀的平方和,另外那个式子是否交换位置是无影响的.可以看成常数。
因此最后我们就变成了找到下面这个式子的最小值:
前面说过了,状态机肯定不行有后效性.
因此考虑记录下所有$a$数组前缀的所有可能值即可。
得到$a$的所有可能镜象的考虑b用下式子可以得到$ans$了.
具体的类似分组背包看代码就行了.
因为前缀只可能由前一个位置递推过来不可能说直接由前面其他的位置跳过来,那样的话从该位置到$i$中间的数值必须是0,而因为$a[i]\geq 1$因此该转移是没问题的
}//得到a的前缀所有可能方案后对称的就可以直接O(1)的得到b的方案
}