与えられた頂点のK個からなる部分集合について、最適なPの座標はx座標の中央値となる。 なので、Pの候補は与えられた頂点のx座標に限られる。 これらx座標を昇順に見ていく。(以下、x[k]<x[k+1]とする) P=x[0]としてとりあえず近いK個を集合Lに入れておく。残った頂点は集合Rに入っているとする。 x[k] -> x[k+1]と変化したとする。x[k]のときの最適な構成Lから、x[k+1]のとき</x[k+1]とする)>…

素朴に考えると dp[i][j] := i個の要素を使って、前の部品のprofit factorがjのときの最大profit のようなDPを得る。 例えば、サンプルの入力で6, 8を使うと dp[2][8] = 6*8 のようになる。 この方法には問題が3つあるが、どれも対処できる。 (1) profit fac…