下降子序列的最小划分等于最长不下降子序列的长度究竟是为什么

P1233 木棍加工

有人说根据dilworth定理,但我百度了这玩意,有点看不懂。。。。
by 取啥名好 @ 2020-09-28 13:26:36


~~bfs~~
by SfumatoCannon_ @ 2020-09-28 13:26:48


好像是先证明LIS>=M 再证明LIS<=M (LIS是最长上升/不降子序列,M是划分数) ~~学这些证明干啥知道能这么干不就行了~~
by Ryan_jiang07 @ 2021-08-28 11:34:12


|