Solution WISEQ

Trương Tuấn Tú 2022-01-10 11:47:51 2022-01-10 11:50:22

Subtask 1 : n <= 20 ; W <= S

  • Sử dụng Backtracking
  • ĐPT : O(2 ^ n)

Sutask 2 : n <= 50; W = S

  • Chính là bài dãy con tăng (LIS) cơ bản
  • ĐPT : O(n ^ 2)

Subtask 3 : n <= 50; W <= S

  • Quy hoạch động : F[i][j] là dãy con tăng dài nhất từ 1 đến i có tổng trọng số không quá j.
  • ĐPT : O(n ^ 2 * W)

Subtask 4 : n <= 500; W <= S

  • Cải tiến từ Subtask 3 : Ta sẽ sử dụng 1 cây BIT để quản lí
  • ĐPT : O(n * log(n) * W)

Subtask 5: n <= 50000; W = S

  • Cải tiến từ subtask 2 : Ta sẽ sử dụng 1 cây BIT để quản lí
  • ĐPT O(n * log(n))