Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán rời rạc] Phản xích lớn nhất trong poset chia hết

    Cho tập số nguyên dương phân biệt, xét thứ tự bộ phận a⪯b  ⟺  a∣ba\preceq b \iff a\mid ba⪯b⟺a∣b. Một phản xích (antichain) là tập con mà không phần tử nào chia hết phần tử khác. Theo định lý Dilworth, kích thước phản xích lớn nhất bằng số chuỗi nhỏ nhất phủ hết poset, tính được bằng nnn trừ đi ghép cặp cực đại trên DAG quan hệ. Hãy in kích thước phản xích lớn nhất.

    • Định dạng đầu vào:

      Dòng đầu: nnn. Dòng sau: nnn số nguyên dương phân biệt.

    • Ràng buộc đầu vào:

      1≤n≤3001 \le n \le 3001≤n≤300, các số trong [1,109][1,10^9][1,109].

    • Định dạng đầu ra:

      Một dòng: kích thước phản xích lớn nhất.

    Ví dụ:

    Đầu vào:

    4
2 3 4 9

    Đầu ra:

    2

    Giải thích:

    Phản xích lớn nhất ví dụ $\{4,9\}$ hoặc $\{2,3\}$... thực ra $\{4,3\}$ hay $\{2,9\}$, kích thước lớn nhất là 2.

    Đang tải editor...