Editorial for Tạo Cây

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Subtask \(1\):

  • Bạn có thể gọi \(DP[i][j]\) khi xét đến đỉnh i, trọng số j có số cách điền mà với mọi điểm liền kề \(\ge\) k.
  • kết quả là tổng \(DP[1][i]\) với mọi \(i\) từ \(1\) đến \(m\).
  • nhận thấy độ phức tạp là \(O(t * n * m^2)\).
  • code: https://ideone.com/jskdXp

Subtask \(2\):

  • bạn có thể thêm \(2\) mảng tiền tố và hậu tố, đỡ tốn \(1\) for như subtask \(1\) thì có thể qua subtask này 😃
  • Độ Phức tạp: \(O(t * n * m)\)
  • code: https://ideone.com/pr1hy3

Subtask \(5\):


Comments

There are no comments at the moment.