Luyện thi cấp tốc

Tác giả:

Dạng bài

Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 977M Input: bàn phím Output: màn hình

XYZ là trung tâm luyện thi đại học lâu đời ở tỉnh Phú Thọ, nơi đây đã sản sinh ra vô số thủ khoa của cả nước. Thành công của trung tâm đến từ bí quyết “Đánh giá năng lực 4.0”. Trung tâm vận hành cách đánh giá dựa trên một siêu máy tính. Giả sử đối tượng học tập còn \(X\) ngày là đến kỳ thi đại học và đối tượng muốn ôn thi \(N\) môn, siêu máy tính sẽ tính được rằng nếu đối tượng học ở trung tâm trong \(j\) ngày để ôn thi môn thứ \(i\) thì sẽ đạt \(A_{i,j}\) điểm. Tất nhiên là càng học nhiều thì điểm sẽ cao lên nên \(A_{i,j} \leq A_{i, j + k} (k \geq 0)\). Dựa vào đánh giá trên trung tâm sẽ tìm ra phương pháp học tập tốt nhất cho đối tượng.

Hôm nay do có một chút trục trặc nên siêu máy tính không thể hoạt động được nữa , bạn hãy viết chương trình giúp trung tâm nhé!!

Input

Dòng đầu tiên chứa 2 số nguyên dương \(N\) và \(X\).
\(N\) dòng tiếp theo, mỗi dòng ghi \(X\) số, số thứ \(j\) là \(A_{i,j}\) (\(A_{i,j} \leq 10^6\)) là số điểm đạt được của môn thứ \(i\) nếu học trong \(j\) ngày.

Output

Hãy in ra một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.

Scoring

Subtask \(1\) (\(30\%\) số điểm): \(N,X \leq 4\)
Subtask \(2\) (\(30\%\) số điểm): \(N \leq 100, X=1\)
Subtask \(3\) (\(40\%\) số điểm): \(N,X \leq 100\)

Example

Test 1

Input

Output

Bình luận

def main():
# Đọc đầu vào
N, X = map(int, input().split()) # N là số môn học, X là số ngày còn lại
A = []

for i in range(N):
    A.append(list(map(int, input().split())))  # Đọc bảng điểm cho mỗi môn học

# Khởi tạo mảng dp: dp[j] là điểm số cao nhất có thể đạt được khi sử dụng j ngày
dp = [0] * (X + 1)  # dp[i] sẽ chứa điểm số lớn nhất với i ngày

# Quá trình tính toán bằng quy hoạch động
for i in range(N):
    # Chúng ta phải lặp ngược từ X đến 0 để tránh việc dùng lại kết quả của chính vòng lặp này
    for j in range(X, 0, -1):
        for k in range(1, j + 1):  # thử tất cả các ngày từ 1 đến j
            dp[j] = max(dp[j], dp[j - k] + A[i][k - 1])

# Kết quả là dp[X], tổng điểm lớn nhất có thể đạt được trong X ngày
print(dp[X])

if name == "main":
main()

4 bình luận nữa