0w1

Dilworth Theorem

POJ 3866 Exclusive Access 2 ( Dilworth Theorem, DP, bitmask )

3866 -- Exclusive Access 2題意: 給一個 N 個無向邊的圖。求一種方案使所有邊定向,並有最短的最長路徑 ( 即不存在環 )。無法到達的點對之間的路徑長不須考慮。資料規模: N ≤ 100 節點為 [ L, Z ] 間的大寫英文字母,數量不超過 15。 TL: 5000 ms ML: 655…

POJ 1065 Wooden Sticks ( Dilworth theorem, LIS )

1065 -- Wooden SticksDilworth Theorem題意: T 筆測資。給 N 個座標,求排序後最少的相鄰對數滿足右邊的點不在以左邊的點為原點的第一象限 ( 在線上也算第一象限 )。資料規模: The input consists of T test cases. The number of test cases (T) is give…