Khái niệm
Cho mảng A có N phần tử và hai số nguyên l, r với 1≤ ax ≤ 105 và 1≤ l≤ r≤ N. Ta có thể chọn bất kỳ phần tử nào của mảng (giả sử ax) và xóa nó, đồng thời xóa tất cả các phần tử bằng ax+1, ax+2 ... ax+R và ax-1, ax-2 ... ax-L khỏi mảng. Bước này sẽ tốn ax điểm. Nhiệm vụ là tối đa hóa tổng chi phí sau khi xóa hết các phần tử khỏi mảng.
Đầu vào
2 1 2 3 2 2 1 l = 1, r = 1
Đầu ra
8
Ở đây, ta chọn 2 để xóa, sau đó (2-1)=1 và (2+1)=3 sẽ bị xóa theo khoảng l và r tương ứng.
Lặp lại cho đến khi 2 bị xóa hoàn toàn. Tổng chi phí = 2*4 = 8.
Đầu vào
2 4 2 10 5 l = 1, r = 2
Đầu ra
18
Ở đây, ta chọn 2 để xóa, sau đó 5 và rồi 10.
Tổng chi phí = 2*2 + 5 + 10 = 19.
Phương pháp
Đầu tiên, xác định số lần xuất hiện của tất cả các phần tử. Giả sử chọn phần tử X, thì tất cả các phần tử trong khoảng [X-l, X+r] sẽ bị xóa. Hiện tại, ta chọn khoảng nhỏ hơn giữa l và r và xác định đến phần tử nào sẽ bị xóa khi chọn X. Kết quả sẽ là lớn nhất giữa các phần tử đã xóa trước đó và khi xóa X. Ta sẽ triển khai quy hoạch động để lưu kết quả của các phần tử đã xóa và áp dụng tiếp.
Ví dụ
// Chương trình C++ tìm chi phí tối đa sau khi xóa tất cả phần tử khỏi mảng
#include <bits/stdc++.h>
using namespace std;
// Hàm trả về chi phí tối đa đạt được
int maxCost(int a[], int m, int L, int R){
int mx1 = 0, k1;
// Tìm phần tử lớn nhất của mảng.
for (int p = 0; p < m; ++p)
mx1 = max(mx1, a[p]);
// Khởi tạo đếm tất cả phần tử bằng 0.
int count1[mx1 + 1];
memset(count1, 0, sizeof(count1));
// Tính tần suất xuất hiện của tất cả phần tử mảng.
for (int p = 0; p < m; p++)
count1[a[p]]++;
// Lưu chi phí của các phần tử bị xóa.
int res1[mx1 + 1];
res1[0] = 0;
// Chọn khoảng nhỏ hơn từ L và R.
L = min(L, R);
for (int num1 = 1; num1 <= mx1; num1++) {
// Xác định đến phần tử nào bị xóa khi chọn num.
k1 = max(num1 - L - 1, 0);
// Lấy tối đa khi chọn phần tử num hoặc không.
res1[num1] = max(res1[num1 - 1], num1 * count1[num1] + res1[k1]);
}
return res1[mx1];
}
// Chương trình chính
int main(){
int a1[] = { 1, 1, 3, 3, 3, 2, 4 }, l1 = 1, r1 = 1;
int a2[] = { 2, 4, 2, 10, 5 }, l2 = 1, r2 = 2;
// Kích thước mảng
int n1 = sizeof(a1) / sizeof(a1[0]);
int n2 = sizeof(a2) / sizeof(a2[0]);
// Gọi hàm tìm chi phí tối đa
cout<<"Chi phí tối đa cho ví dụ đầu tiên: "<< maxCost(a1, n1, l1,r1)<<endl;
cout<<"Chi phí tối đa cho ví dụ thứ hai: "<< maxCost(a2, n2, l2,r2);
return 0;
}
Đầu ra
Chi phí tối đa cho ví dụ đầu tiên:11 Chi phí tối đa cho ví dụ thứ hai:19