【BZOJ1786】[Ahoi2008]Pair 配对时间:2023-03-08 23:32:12 题解: 打表出奇迹 能发现所有ai一定是不减的 其实很好证明啊。。 考虑两个位置x y(y在x右边) x的最优值已经知道了 考虑y处 先让y=x,然后开始变化 因为x处已经是最优的了,所以如果减小,那么一定会增多(或者不变) 说明左边增加的逆序对比右边减少的要多(或者不变) 那现在考虑y处 如果减少,那么左边增加的逆序对会更多 右边减少的会更少 所以一定是不优的 然后就随便dp了 f[i][j] 前i个最大值为j