注:本文中内容来源于2018年集训队论文
定义
偏序关系
设 (R) 是集合 (S) 上的一个二元关系，若 (R) 满足:
- 自反性: (forall xin S)， 有 (x R x)；
- 反对称性: (forall x,yin S)，若有 (x R y, y R x)，则有 (x=y)；
- 传递性: (forall x,y,zin S)，若有 (x R y, y R z)，则有 (x R z)。
则称 (R) 为 (S) 上的非严格偏序关系，记做 (le)。
问题描述
给定正整数 (p)，一张点集为 (V={v_1,v_2...v_n})，边集 (E(|E|=m))的有向无环图 (G) ，及代价函数 ((y,w)(forall i, w_i>0)) 。如果在 (G) 中有 (v_i) 到 (v_j) 的有向路径，那么就有 (v_ile v_j) 的偏序关系。
求点值序列 (f)，满足 (forall v_ile v_j(i,jin[1,n]))，均有 (f_ile f_j)，最小化回归代价:
对于相同的 (p)，这一类问题统称为 (L_p) 问题。
一些约定
Definition: 将序列 (z) 中不超过 (a) 的元素变为 (a)，不小于 (b) 的元素变为 (b) 称为序列 (z) 向集合 (S={a,b}) 取整。
Definition: 点集 (U) 的 (L_p) 均值为满足 (sum_{v_iin U}w_i|y_i-k|^p(1le p<infty)) 或 (max_{v_iin U}w_i|y_i-k|(p=infty)) 最小的 (k)。
特殊情形下的算法
一种贪心做法
给定正整数序列 (y,w)，求单调不减的实数序列 (f)，最小化 (sum_{i=1}^nw_i(f_i-y_i)^2,nle2*10^5)
Lemma: 点集 (U) 的 (L_2) 均值为其加权平均数 (frac{sum_{v_iin U}w_iy_i}{sum_{v_iin U}w_i})
Lemma: (forall1le i<n)，如果有 (y_i>y_{i+1})，那么最优解中一定满足 (f_i=f_{i+1})
直接做单调栈即可。
维护折线算法
给一个 (n) 个点 (n-1) 条边的有向弱连通图 (G=(V,E))，每个点均有点权 (d_i) 和修改耗时 (w_i)。对于每个 (i(1le ile n))，每次修改可以花费 (w_i) 的时间把 (d_i) 加 (1) 或减 (1)，求最小消耗多少时间，使得 (forall(u,v)in E,d_ule d_v。nle3*10^5,1le d_ile10^9,1le w_ile10^4)
折线优化 dp 基础题