\(K\) が固定された場合の問題を考えます．

各 \(1 \leq v \leq N\), \(1 \leq c \leq K\) に対して，\(B_{v,c}= \min\{A_u\ |\ u \in X_c\) かつ DAG において頂点 \(u\) から頂点 \(v\) へ移動できる \(\}\) とします．

ここで各頂点 \(v\) に対し \(B_{v,1} \leq \cdots \leq B_{v,K}\) を要請しても最適解は変わりません．

証明の概略: 最適解を一つとる．各頂点 \(v\) について，\(v \in X_c\) なら \(A_v\) の値を \(B_{v,c}\) にしておく． この \(A_v\) を用いて，\(v\) の昇順に各 \(v\) を \(K\) 個の集合に貪欲に振り分けて行くとうまく行く．

各 \(1 \leq i \leq N\), \(0 \leq j \leq \max(A)\) に対して，\(P_{i,j}=\max(c\ |\ c=0\ \mathrm{ or }\ B_{i,c} \leq j)\) と定義します．

\(P_{i,j}\) の満たすべき制約を列挙します．

• \(0 \leq P_{i,j} \leq K\)
• \(1 \leq P_{i,A_i}\)
• 各 \(i\) に対し，\(P_{i,j}\) は \(j\) について広義単調増加．
• DAG の各辺 \((u,v)\) に対し，\(P_{u,j} \leq P_{v,j}\)

また，\(P\) を決めたときのスコアを考えます． 各 \(i\) について，\(j<A_i\) かつ \(P_{i,A_i}=P_{i,j}\) となる \(j\) の個数を \(C_i\) とおくと，最終的なスコアは \(\sum_{1 \leq i \leq N} A_i-C_i\) になります． よって \(\sum C_i\) の最小化を考えればよいです．．

ところで，\(C_i\) の定義を次のように変更しても問題ありません．

• \(C_i=\sum_{0 \leq j < A_i} \max(P_j-P_i+1,0)\)

\(P_{i,j}\) の満たすべき制約と，そのコストが定式化できましたが，これらはすべて LP の形で書けます． この双対を考えると最小費用流問題が登場するので，これを解けばよいです．

最小費用流は不辺が存在していますが，適切なポテンシャルを計算 (例えば \(P_{i,j}\) のポテンシャルを \(j\) とする) することでコストを非負の場合に帰着することができます．

また，すべての \(K\) について解くためには，最小費用流のコストを傾きごとに求めるようにすれば良いです．

計算量は \(O(N^2\max(A)^2\log(N\max(A))\) になります．

回答例(C++)