2012-03-30から1日間の記事一覧
問題概要 数字のペアの列(長さN 解説 某所で日本語解説を見てしまっていたので殆ど自分で考えずに解いてしまった。 Dilworthの定理より、最小パス被覆を求める代わりに最大反鎖のサイズを求める。これはペアをソートした後第二要素の最長狭義減少列を求めれ…
問題概要 いわゆる連鎖行列積。復元もあり。 解法 [from, to)型のDPの典型例。
問題概要 数字のペアの列(長さN 解説 某所で日本語解説を見てしまっていたので殆ど自分で考えずに解いてしまった。 Dilworthの定理より、最小パス被覆を求める代わりに最大反鎖のサイズを求める。これはペアをソートした後第二要素の最長狭義減少列を求めれ…
問題概要 いわゆる連鎖行列積。復元もあり。 解法 [from, to)型のDPの典型例。