私はいくつかの間隔I = {I(1), I(2), ..., I(m)}
を与えましたI(i) = [a_i, b_i] (1<=a_i<=b_i<=n)
。間隔が互いにカバーしていると思われるかもしれません (英語が下手で申し訳ありません) {[1,5], [3,6]}, {[2,5], [5,7]}
。I{[1,1], [2,2], ..., [n,n]}
に含まれている必要があります。
としましょうC(i) = b_i - a_i + 1
。
{I(c_1), I(c_2), ..., I(c_k)}
お互いに重なり合っていないものを見つけたいC(c_1) + C(c_2) + ... + C(c_k) = T. (1 <= T <= n)
.
Subset Sum問題を使用してDPソリューションを見つけることができO(n*T)
ました.NPだと思いますが、よくわかりません。以上を最適化できますO(n*T)
か?