和拟阵一样,做一道联合省选题的时候遇到了这个,之前高爸也屡次♂邀请♂我学它,于是就有了本文。

保序回归问题

对于有向无环图,定义代价函数和初态函数,求一个终态函数使得

  • ,则

)。

另一种形式的保序回归问题,以后再讨论。

特殊情形

,一定存在一个最优解使得

我们可以对做整体二分,对于区间假设其中点为,那么我们强制,也就是说的取值只有,求最小回归代价。

这是一个 01 决策问题,可以转化为最小权闭合子图问题。

在得到每个点的决策后,对于两边再分别整体二分即可。

最大权闭合子图问题

最大权闭合子图问题为:给出一个带点权的有向图,要求选择的一个子集使得点权和最大,同时满足:若被选那么的后继也要被选。

这个问题可以利用最小割解决。直接把这个有向图当作网络图,中的边容量都为无限大。加入一些新的边:

  • 的点权为正,则加一条的容量为点权的边;
  • 的点权为负,则加一条的容量为点权绝对值的边。

对这个图跑最小割,答案即为正权点的和减去最小割的容量。

可以理解为:割一条的边代表不选这个点,割一条的边代表选这个点。

一般情形

只要,那么我们将在上二分更改为在实数集上整体二分即可求出关于某个精度的近似解。

在信息学竞赛中,一般求的是整数解,因此在整数集上二分也可。

参考文献

高睿泉,《浅谈保序回归问题》,IOI2018 中国国家集训队论文。