Chương trình tìm đội hình tốt nhất không xung đột trong Python

Cho scores và ages của các cầu thủ. Chọn đội có tổng điểm cao nhất. Xung đột: cầu thủ trẻ hơn có điểm cao hơn cầu thủ lớn tuổi. Tìm max tổng điểm không xung đột.

Ví dụ: scores=[5,7,9,14,19], ages=[5,6,7,8,9] → 54 (chọn tất cả, điểm tăng cùng tuổi).

Giải thuật (DP sau khi sắp xếp theo tuổi)

1. Ghép cặp (age, score), sắp xếp theo tuổi (tuổi bằng thì theo điểm).
2. dp[i] = max tổng điểm đội kết thúc bằng cầu thủ i.
3. dp[i] = score[i] + max(dp[j]) với j < i và score[j] <= score[i].
4. Kết quả = max(dp).

Ví dụ minh họa

def solve(scores, ages):
    sa = [[a, s] for a, s in zip(ages, scores)]
    sa.sort()
    scores = [s for a, s in sa]
    maxScore = 0
    n = len(scores)
    dp = [0] * n
    for i in range(n):
        score = scores[i]
        dp[i] = score
        for j in range(i):
            if scores[j] <= score:
                dp[i] = max(dp[i], dp[j] + score)
        maxScore = max(maxScore, dp[i])
    return maxScore

scores = [5,7,9,14,19]
ages = [5,6,7,8,9]
print(solve(scores, ages))

Đầu vào

[5,7,9,14,19], [5,6,7,8,9]

Đầu ra

54