VOJ - CUTSEQS
Source: CUTSEQS
Tags: Dynamic Programming, Data Structures
Problem:
Cho dãy A có N số nguyên, tìm cách cắt dãy số thành một số dãy số (giữ nguyên thứ tự) thỏa mãn:
- Tổng của mỗi dãy số không lớn hơn M.
- Tổng của các số lớn nhất trong mỗi dãy là nhỏ nhất.
Nếu không có cách cắt, in ra -1.
1 ≤ N ≤ 1e5.
0 ≤ A[i] ≤ 1e6.
M < 2^63.
Ví dụ:
Input:
8 17
2 2 2 8 1 8 2 1
Output:
12
Explanation:
Cắt thành các dãy như sau (2, 2, 2), (8, 1, 8), (2, 1).
Solution:
Nếu có phần tử A[i] nào lớn hơn M thì không có cách cắt, in ra -1.
Có thể dễ dàng nhìn ra công thức DP O(N^2) như sau, gọi F[i] là đáp án của dãy từ 1 đến i:
F[i] = min(F[j] + max(A[j + 1], A[j + 2], ..., A[i])),
trong đó j thỏa mãn: j < i, tổng A[j + 1] + A[j + 2] + ... + A[i] ≤ M.
Vậy giải quyết bài toán này trong O(N) hoặc O(NlogN) như thế nào?
Gọi một vị trí k là vị trí thỏa mãn những điều kiện sau: k thuộc đoạn từ j đến i, A[k] lớn hơn tất cả phần tử từ k + 1 đến i.
Tại một vị trí i, ta có thể tìm ra vị trí k ngay trước nó bằng thủ thuật stack cơ bản.
while stack không rỗng và top stack <= A[i] do stack pop
Tuy nhiên, chú ý điều kiện k phải nằm trong vùng mà j thỏa, tức là tổng A[k + 1] + A[k + 2] + ... + A[i] ≤ M. Ta có thể dễ dàng tìm được vị trí j xa i nhất thỏa điều kiện này bằng 2 pointers hoặc binary search, vậy để đảm bảo những vị trí k trong stack thỏa, ta cần cài đặt một deque thay vì stack để có thể pop những phần tử đầu không thỏa ra khỏi deque.
while deque front < j do deque pop front
Gọi prev[i] là vị trí k ngay trước i. Sau khi đã tìm được các vị trí k, ta để ý như sau, F[i] = min(F[j] + max(A[j + 1], A[j + 2], ..., A[i])) lúc này có thể rút thành công thức sau F[i] = min(F[prev[k]] + A[k]). Tại sao lại như vậy? Để ý rằng A[k] là max trong đoạn k + 1 ... i và vì prev[k] là phần từ max ngay trước k, vậy trong đoạn prev[k] + 1 ... k, A[k] vẫn là max (nếu prev[k] < j thì prev[k] = j).
Ngay lúc này ta rút được một giá trị chỉ phụ thuộc vào k! Vậy rõ ràng công việc của ta lúc này là tìm giá trị min tương ứng với từng vị trí k trong deque mà ta đã tạo. Công việc này có thể làm nhanh bằng cách sử dụng Interval Tree hoặc một DS nào đó khác (có người cài DS giải bài này bằng heap, cài tay và lưu lại vị trí i trong heap để có thể update, bạn có thể thử ( ͡° ͜ʖ ͡°)). Chỉ cần để ý khi update là xóa phần tử bị pop khỏi deque (nếu làm IT thì có thể thay giá trị tại vị trí đấy bằng +inf rồi update lại chẳng hạn) và quan trọng nhất là phải update lại thằng k ở đầu deque (deque front) vì prev[k] của nó bị đổi thành thằng j.
Độ phức tạp deque O(2N), IT O(logN). Tổng cộng là O(2N+NlogN).
Code:
#include <iostream>
#include <queue>
using namespace std;
const unsigned long long oo = 1ll << 63;
int n, a[100015];
unsigned long long m, IT[400015], f[100015];
deque <int> pos;
void ITbuild(int k, int l, int r) {
IT[k] = oo;
if (l == r) return;
ITbuild(2 * k, l, (l + r) / 2);
ITbuild(2 * k + 1, (l + r) / 2 + 1, r);
}
void ITupdate(int x, unsigned long long v, int k, int l, int r) {
if (x < l || r < x) return;
if (l == r) IT[k] = v;
else {
ITupdate(x, v, 2 * k, l, (l + r) / 2);
ITupdate(x, v, 2 * k + 1, (l + r) / 2 + 1, r);
IT[k] = min(IT[2 * k], IT[2 * k + 1]);
}
}
int main() {
cin >> n >> m;
ITbuild(1, 1, n);
unsigned long long sum = 0;
for (int i = 1, j = 1; i <= n; i++) {
cin >> a[i];
if (a[i] > m) {
cout << -1; return 0;
}
sum += a[i];
while (sum > m) sum -= a[j++];
while (!pos.empty() && a[pos.back()] <= a[i])
ITupdate(pos.back(), oo, 1, 1, n), pos.pop_back();
while (!pos.empty() && pos.front() < j)
ITupdate(pos.front(), oo, 1, 1, n), pos.pop_front();
if (pos.empty()) ITupdate(i, a[i] + f[j - 1], 1, 1, n);
else
ITupdate(pos.front(), a[pos.front()] + f[j - 1], 1, 1, n),
ITupdate(i, a[i] + f[pos.back()], 1, 1, n);
pos.push_back(i);
f[i] = IT[1];
}
cout << f[n];
}
Tags: Dynamic Programming, Data Structures
Problem:
Cho dãy A có N số nguyên, tìm cách cắt dãy số thành một số dãy số (giữ nguyên thứ tự) thỏa mãn:
- Tổng của mỗi dãy số không lớn hơn M.
- Tổng của các số lớn nhất trong mỗi dãy là nhỏ nhất.
Nếu không có cách cắt, in ra -1.
1 ≤ N ≤ 1e5.
0 ≤ A[i] ≤ 1e6.
M < 2^63.
Ví dụ:
Input:
8 17
2 2 2 8 1 8 2 1
Output:
12
Explanation:
Cắt thành các dãy như sau (2, 2, 2), (8, 1, 8), (2, 1).
Solution:
Nếu có phần tử A[i] nào lớn hơn M thì không có cách cắt, in ra -1.
Có thể dễ dàng nhìn ra công thức DP O(N^2) như sau, gọi F[i] là đáp án của dãy từ 1 đến i:
F[i] = min(F[j] + max(A[j + 1], A[j + 2], ..., A[i])),
trong đó j thỏa mãn: j < i, tổng A[j + 1] + A[j + 2] + ... + A[i] ≤ M.
Vậy giải quyết bài toán này trong O(N) hoặc O(NlogN) như thế nào?
Gọi một vị trí k là vị trí thỏa mãn những điều kiện sau: k thuộc đoạn từ j đến i, A[k] lớn hơn tất cả phần tử từ k + 1 đến i.
Tại một vị trí i, ta có thể tìm ra vị trí k ngay trước nó bằng thủ thuật stack cơ bản.
while stack không rỗng và top stack <= A[i] do stack pop
Tuy nhiên, chú ý điều kiện k phải nằm trong vùng mà j thỏa, tức là tổng A[k + 1] + A[k + 2] + ... + A[i] ≤ M. Ta có thể dễ dàng tìm được vị trí j xa i nhất thỏa điều kiện này bằng 2 pointers hoặc binary search, vậy để đảm bảo những vị trí k trong stack thỏa, ta cần cài đặt một deque thay vì stack để có thể pop những phần tử đầu không thỏa ra khỏi deque.
while deque front < j do deque pop front
Gọi prev[i] là vị trí k ngay trước i. Sau khi đã tìm được các vị trí k, ta để ý như sau, F[i] = min(F[j] + max(A[j + 1], A[j + 2], ..., A[i])) lúc này có thể rút thành công thức sau F[i] = min(F[prev[k]] + A[k]). Tại sao lại như vậy? Để ý rằng A[k] là max trong đoạn k + 1 ... i và vì prev[k] là phần từ max ngay trước k, vậy trong đoạn prev[k] + 1 ... k, A[k] vẫn là max (nếu prev[k] < j thì prev[k] = j).
Ngay lúc này ta rút được một giá trị chỉ phụ thuộc vào k! Vậy rõ ràng công việc của ta lúc này là tìm giá trị min tương ứng với từng vị trí k trong deque mà ta đã tạo. Công việc này có thể làm nhanh bằng cách sử dụng Interval Tree hoặc một DS nào đó khác (có người cài DS giải bài này bằng heap, cài tay và lưu lại vị trí i trong heap để có thể update, bạn có thể thử ( ͡° ͜ʖ ͡°)). Chỉ cần để ý khi update là xóa phần tử bị pop khỏi deque (nếu làm IT thì có thể thay giá trị tại vị trí đấy bằng +inf rồi update lại chẳng hạn) và quan trọng nhất là phải update lại thằng k ở đầu deque (deque front) vì prev[k] của nó bị đổi thành thằng j.
Độ phức tạp deque O(2N), IT O(logN). Tổng cộng là O(2N+NlogN).
Code:
#include <iostream>
#include <queue>
using namespace std;
const unsigned long long oo = 1ll << 63;
int n, a[100015];
unsigned long long m, IT[400015], f[100015];
deque <int> pos;
void ITbuild(int k, int l, int r) {
IT[k] = oo;
if (l == r) return;
ITbuild(2 * k, l, (l + r) / 2);
ITbuild(2 * k + 1, (l + r) / 2 + 1, r);
}
void ITupdate(int x, unsigned long long v, int k, int l, int r) {
if (x < l || r < x) return;
if (l == r) IT[k] = v;
else {
ITupdate(x, v, 2 * k, l, (l + r) / 2);
ITupdate(x, v, 2 * k + 1, (l + r) / 2 + 1, r);
IT[k] = min(IT[2 * k], IT[2 * k + 1]);
}
}
int main() {
cin >> n >> m;
ITbuild(1, 1, n);
unsigned long long sum = 0;
for (int i = 1, j = 1; i <= n; i++) {
cin >> a[i];
if (a[i] > m) {
cout << -1; return 0;
}
sum += a[i];
while (sum > m) sum -= a[j++];
while (!pos.empty() && a[pos.back()] <= a[i])
ITupdate(pos.back(), oo, 1, 1, n), pos.pop_back();
while (!pos.empty() && pos.front() < j)
ITupdate(pos.front(), oo, 1, 1, n), pos.pop_front();
if (pos.empty()) ITupdate(i, a[i] + f[j - 1], 1, 1, n);
else
ITupdate(pos.front(), a[pos.front()] + f[j - 1], 1, 1, n),
ITupdate(i, a[i] + f[pos.back()], 1, 1, n);
pos.push_back(i);
f[i] = IT[1];
}
cout << f[n];
}
Nhận xét
Đăng nhận xét