Bình luận

• 
  

  3

  

  YougiTuber  đã bình luận lúc 8, Tháng 7, 2025, 15:16

  Spoil⚠️

  Link 1433F - Zero Remainder Sum

  Tag

  Quy hoạch động

  Đối với mỗi hàng, tạo ra mảng quy hoạch động ~f[i][j][r]~ là tổng lớn nhất thu được khi xét đến số thứ ~i~ của hàng đó, sử dụng không quá ~j~ số, và tạo ra số dư là ~r~

  Công thức

  ~f[i][j][r] = max(f[i][j-1][r], f[i-1][j-1][(r-a[i])\%k] + a[i])~

  Sau đó, từ mảng ~f~, ta tạo ra mảng ~b~ với ~b[i][r]~ là tổng lớn nhất thu được nếu xét hàng ~i~, tạo ra số dư ~r~

  ~b[i][r] = f[m][m/2][r]~

  Với ~f~ là mảng quy hoạch động được tính đối với hàng thứ ~i~

  Cuối cùng dựng mảng ~g~ với ~g[i][r]~ là tổng lớn nhất thu được khi xét đến hàng thứ ~i~ và tổng dư ~r~

  ~g[i][r] = max(g[i][r], g[i-1][(r-x)\%k] + b[i][x]~

  Với ~x~ là các số dư có thể cho hàng thứ ~i~

  Note

  Khởi tạo:

  ~f[0][0][0] = 0~, với các ~f[i][j][r]~ khác, gán bằng ~-\infty~

  ~g[0][0] = 0~, với các ~g[0][r]~ khác, gán bằng ~-\infty~

  Kết quả cuối cùng là ~g[n][0]~

  Độ phức tạp: ~O(n\cdot m^2 \cdot k)~

  Submission

  https://codeforces.com/contest/1433/submission/181035868