根据题意建立流模型。
\(s->i\)连接\(p_i\)
\(i->t\)连接\(s_i\)
\(i->j,i<j\)连接\(c\)
发现由于数据范围，不太能做。
这个模型事实上是经典的二元关系网络流。
如果一个点被分到\(s\)集合则把它标为\(0\)，分到\(t\)集合就标为\(1\)。
问题转化成：给每个点一个标号，如果\(i\)是\(0\)则获得\(s_i\)代价，是\(1\)则获得\(t_i\)代价。
如果存在\(i<j\)且\(i\)是\(0\)\(j\)是\(1\)，则代价额外加上\(c\)。
显然考虑dp，设\(f_{i,j}\)表示前缀\([1,i]\)有\(j\)个\(0\)，后面没有填的最小费用。
则我们就知道前面有多少个\(1\)，代价可以轻松计算。
由于题目空间卡，要滚动数组。
虽然时间复杂度是\(O(n^2)\)，但是常数小，可以过。
考虑更为优秀的做法，用经典的贪心调整法。
把每个数的标号初始成\(0\)，接着考虑把一个点变成\(1\)。
则代价+=前面\(0\)个数，-=后面\(1\)个数，+=\(t_i-s_i\)。
观察发现随着一些\(0\)变成\(1\)，每个位置的代价会恒定减去\(c\)。
如果位置\(i,j\)，\(i\)比\(j\)优，以后\(i\)也比\(j\)优。
于是排序后贪心选即可，时间复杂度是\(O(n\log_2n)\)。
原文：https://www.cnblogs.com/ctmlpfs/p/14880291.html