Phân tích bài toán

Khi gặp một con quái vật, người chơi có hai lựa chọn: thả hoặc tiêu diệt. Mỗi lựa chọn mang lại số điểm kinh nghiệm khác nhau. Mục tiêu là tìm cách tối đa hóa tổng điểm kinh nghiệm.

Các trường hợp tiếp cận ban đầu

Phương pháp tham lam đơn giản

Tư tưởng ban đầu là so sánh điểm nhận được từ việc thả và tiêu diệt từng con quái, chọn phương án nào cho điểm cao hơn.

n = int(input())
health_values = list(map(int, input().split()))

total_exp = 0
victories = 0
for position in range(1, n+1):
    defeat_gain = health_values[position-1] + ((victories+1) % 10) * health_values[position-1]
    if defeat_gain > position:
        total_exp += defeat_gain
        victories += 1
    else:
        total_exp += position
print(total_exp)

Tuy nhiên, cách tiếp cận này có lỗi vì không tính đến mối liên hệ giữa số lượng quái đã tiêu diệt trước đó với điểm thưởng, đặc biệt khi vượt quá 10 con quái thì giá trị modulo sẽ thay đổi đột ngột.

Phương pháp quy hoạch động cơ bản

Sử dụng mảng dp[i][j] để biểu diễn điểm tối đa khi đến vị trí thứ i và đã tiêu diệt tổng cộng j con quái.

n = int(input())
health_values = list(map(int, input().split()))

dp_table = [[0] * (n+1) for _ in range(n+1)]
for pos in range(1, n+1):
    dp_table[pos][0] = dp_table[pos-1][0] + pos
    for count in range(1, pos+1):
        current_reward = (count % 10) * health_values[pos-1] + health_values[pos-1]
        dp_table[pos][count] = max(
            dp_table[pos-1][count-1] + current_reward,
            dp_table[pos-1][count] + pos
        )
print(dp_table[n][n])

Giải pháp này có độ phức tạp O(n²) nên không phù hợp với giới hạn thời gian của đề bài.

Giải pháp tối ưu

Tư tưởng giải pháp

Điểm mấu chốt là điểm thưởng chỉ phụ thuộc vào số lượng quái đã tiêu diệt modulo 10, không phải tổng số thực tế. Do đó, chỉ cần xét tối đa 10 trạng thái tại mỗi vị trí.

Sử dụng mảng dp[m] để lưu điểm tối đa khi số quái đã tiêu diệt modulo 10 bằng m. Với mỗi con quái, cập nhật trạng thái mới trong mảng riêng để tránh xung đột trong cùng vòng lặp.

Cài đặt cuối cùng

n = int(input())
health_values = list(map(int, input().split()))

current_state = [float('-inf')] * 10
current_state[0] = 0

for position in range(1, n+1):
    next_state = [float('-inf')] * 10
    
    for mod_val in range(min(position, 10)):
        if current_state[mod_val] != float('-inf'):
            # Lựa chọn thả quái
            release_value = current_state[mod_val] + position
            next_state[mod_val] = max(next_state[mod_val], release_value)
            
            # Lựa chọn tiêu diệt quái
            new_mod = (mod_val + 1) % 10
            defeat_value = health_values[position-1] * (1 + new_mod) + current_state[mod_val]
            next_state[new_mod] = max(next_state[new_mod], defeat_value)
    
    current_state = next_state

result = max(current_state)
print(result)