题解：P14092 [ICPC 2023 Seoul R] M. S. I. S.

· · 题解

思路

观察可得构造后一列中较大数均可产生贡献。

数据 O(n^2) 可过，考虑 dp。

先将较大数存入答案。

每一列可以向两个数都大于本身的列转移，权值为较小数。

暴力转移即可。