Dilworth定理

· · 个人记录

覆盖整个序列的最少的最长不上升子序列的个数，等价于LIS

覆盖整个序列的最少的最长不下降子序列的个数，等价于LDS

求解二维严格升序LIS时，x1<x2&&y1<y2,需要将横坐标升序，横坐标相同纵坐标降序 对纵坐标求解最长上升子序列

求解二维不严格升序LIS时，x1<=x2&&y1<=y2,需要将横坐标升序，横坐标相同纵坐标降序 对纵坐标求解最长不下降子序列