NOI 2019 Finals - Feast
概要
問題へのリンク
Author : Cyanmond
解法 1
まず、正の値が連続する部分は合わせて$ 1つの要素として良いことがわかる。同様に負の値が連続する部分についても同じことが言える。また、左端に負の値がある場合、右端に負の値がある場合それは無視して良い。
その後、数列内の正の値が高々$ K個になるまで以下の操作を行う。
絶対値が最小の要素を選び、左右の要素とマージする。
以上は$ O(N \log N)でシミュレーションできて十分高速。またこの問題では要求されていないが、全ての$ K \ (1 \leq K \leq N)について$ O(N \log N)で合わせて答えを求めることができる。
解法 2
小課題 6 では$ O(NK)の dp 解法を用いることができる。
dp のテーブルをうまく定義すると、いわゆる Monge dp でこの問題を$ O(N \log \sum_{k=1}^{N}|A|)で解ける。
解法 3
計算量$ O(N \log N)でこちらも全ての$ K \ (1 \leq K \leq N)について答えを求めることができるが、定数倍が重い。