Bài toán: Cắm hoa

Mô tả

Người ta có W bó hoa và V lọ hoa, với W ≤ V. Các bó hoa được đánh số từ 1 đến W, các lọ hoa được đánh số từ 1 đến V.

Với mỗi bó hoa i và lọ hoa j, nếu cắm bó hoa i vào lọ hoa j thì nhận được điểm thẩm mỹ A[i][j].

Cần cắm mỗi bó hoa vào đúng một lọ, mỗi lọ nhiều nhất một bó hoa.

Ngoài ra phải thỏa mãn quy tắc thứ tự:

• Nếu i < k và bó hoa i được cắm vào lọ j,
• còn bó hoa k được cắm vào lọ t,
• thì bắt buộc j < t.

Nói cách khác, thứ tự các bó hoa phải được giữ nguyên theo thứ tự các lọ được chọn.

Hãy tìm tổng điểm thẩm mỹ lớn nhất có thể đạt được.

Dữ liệu vào

Đọc từ tệp CAMHOA.INP:

• Dòng đầu chứa hai số nguyên W, V.
• W dòng tiếp theo, dòng thứ i chứa V số nguyên A[i][1], A[i][2], ..., A[i][V].

Dữ liệu ra

Ghi ra tệp CAMHOA.OUT:

• Một số nguyên duy nhất là tổng điểm thẩm mỹ lớn nhất.

Giới hạn

• 1 ≤ W ≤ V ≤ 1000
• -500 ≤ A[i][j] ≤ 500

Ví dụ

CAMHOA.INP

3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

CAMHOA.OUT

53

Giải thích ví dụ

Một cách cắm tối ưu là:

• bó 1 vào lọ 2
• bó 2 vào lọ 4
• bó 3 vào lọ 5

Tổng điểm nhận được là:

23 + 10 + 20 = 53

Gợi ý

Đây là bài toán quy hoạch động.

Gọi dp[i][j] là tổng điểm lớn nhất khi xét i bó hoa đầu tiên và j lọ đầu tiên.

Có hai lựa chọn:

• Không dùng lọ j
• Cắm bó hoa thứ i vào lọ j

Công thức:

dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + A[i][j])

Kết quả là dp[W][V].

Phân mức gợi ý

• Subtask 1 (20 điểm): W = 1
• Subtask 2 (20 điểm): W, V ≤ 20
• Subtask 3 (30 điểm): W, V ≤ 200
• Subtask 4 (30 điểm): Không có ràng buộc thêm