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;
}