Bài toán điểm số lớn nhất

Bài toán điểm số lớn nhất

Trong một lần đi hội chợ, Nam tham gia trò chơi trúng thưởng với luật chơi được mô tả như sau: Có một băng số hình chữ nhật được chia ra làm N ô vuông, đánh số từ trái qua phải bắt đầu từ 1 đến N. Trên ô vuông thứ i người ta ghi một số nguyên ai (1 i ≤ N). Ở một lượt chơi, trước tiên người chơi sẽ được ban tổ chức cho bốc thăm để nhận được hai số nguyên dương x, y (1 ≤ x ≤ y ≤ N), sau đó trong phạm vi dãy ô từ ax đến ay, người chơi được quyền lựa chọn một dãy các ô liên tiếp nhau; giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn dãy các ô ai, ai+1, …, ai+k; khi đó điểm số mà người chơi đạt được sẽ là: ai + ai+1 + … + ai+k   (x ≤ i ≤ i+k ≤ y)

Yêu cầu: Với hai số x, y bốc thăm được từ một lượt chơi, hãy tính số điểm lớn nhất mà Nam có thể đạt được.

Dữ liệu: Vào từ file văn bản DIEMSO.INP có nội dung:

  • Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 5.104 ) là số lượng ô của băng số;
  • Dòng thứ hai chứa N số nguyên a1, a2, …, aN (| ai | ≤ 15.103) là các số ghi trên băng số;
  • Dòng thứ ba chứa số nguyên dương M (1 ≤ M ≤ 5) là số lượt chơi mà Nam tham gia;
  • Trong M dòng tiếp theo; dòng thứ i ghi hai số xi, yi là hai số Nam bốc thăm được ở lượt chơi thứ i.

Các số trên cùng dòng viết cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản DIEMSO.OUT gồm M dòng, mỗi dòng là điểm số lớn nhất mà Nam có thể đạt được tương ứng với lượt chơi trong file DIEMSO.INP.

Ví dụ:

DIEMSO.INP

DIEMSO.OUT

5

-2  -6  7  -5  10

2

2 3

1 5

7

12

 

 

Cài đặt thuật toán quy hoạch động

Để giải bài toán này, ta có thể áp dụng kỹ thuật quy hoạch động (dynamic programming).

Gọi F[i] là số điểm lớn nhất có thể đạt được khi lựa chọn một dãy các ô liên tiếp từ ô 1 đến ô i. Ta có thể tính giá trị F[i] bằng cách sử dụng công thức sau:

F[i] = max(a[i], F[i-1] + a[i])

Trong đó a[i] là giá trị của ô thứ i trên băng số, và max(a[i], F[i-1] + a[i]) là giá trị lớn nhất có thể đạt được khi lựa chọn một dãy các ô liên tiếp từ ô 1 đến ô i.

Sau khi tính được các giá trị F[i], để tìm số điểm lớn nhất có thể đạt được trong một lượt chơi, ta chỉ cần tìm giá trị lớn nhất trong đoạn [x, y] của mảng F.

Độ phức tạp của giải thuật này là O(NM), với N là số lượng ô của băng số và M là số lượt chơi.

Cài đặt bài toán điểm số lớn nhất với Python

# Bước 1: Đọc dữ liệu từ file DIEMSO.INP và lưu vào các biến tương ứng
with open('DIEMSO.INP', 'r') as f:
    n = int(f.readline().strip())
    a = list(map(int, f.readline().strip().split()))
    m = int(f.readline().strip())
    queries = [tuple(map(int, line.strip().split())) for line in f]

# Bước 2: Sử dụng phương pháp tính prefix sum để tính tổng trọng số các dãy con liên tiếp của mảng a
prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
    prefix_sum[i] = prefix_sum[i - 1] + a[i - 1]

# Bước 3: Đọc từng cặp (x, y) từ file DIEMSO.INP và tính tổng trọng số lớn nhất của các dãy con liên tiếp trong phạm vi từ x đến y
with open('DIEMSO.OUT', 'w') as f:
    for x, y in queries:
        max_sum = None
        for i in range(x, y + 1):
            for j in range(i, y + 1):
                current_sum = prefix_sum[j + 1] - prefix_sum[i]
                if max_sum is None or current_sum > max_sum:
                    max_sum = current_sum
        f.write(str(max_sum) + '\n')

Cài đặt bài toán điểm số lớn nhất với C++

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 50005;

int N, M;
int a[MAXN];
vector<int> sum[MAXN];

void precompute() {
    for (int i = 1; i <= N; i++) {
        sum[i].push_back(a[i]);
        for (int j = i+1; j <= N; j++) {
            sum[j].push_back(sum[j-1].back() + a[j]);
        }
    }
}

int solve(int x, int y) {
    int max_sum = a[x];
    for (int i = x; i <= y; i++) {
        int s = sum[i][y-i];
        max_sum = max(max_sum, s);
        if (s < 0) {
            break;
        }
    }
    return max_sum;
}

int main() {
    ifstream in("DIEMSO.INP");
    ofstream out("DIEMSO.OUT");
    in >> N;
    for (int i = 1; i <= N; i++) {
        in >> a[i];
    }
    precompute();
    in >> M;
    for (int i = 1; i <= M; i++) {
        int x, y;
        in >> x >> y;
        out << solve(x, y) << endl;
    }
    return 0;
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *