Hướng dẫn cho CARDGAME (OLP MT&TN 2023 Sơ Loại Chuyên Tin)
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10^{2}\).
Tutorial
Cách giải ngây thơ nhất cho bài toán là ta duyệt \(\mathcal{O}(n^{2})\) đoạn con, sau đó tìm max và tổng trong \(\mathcal{O}(n)\).
Độ phức tạp: \(\mathcal{O}(n^{3})\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
int numCard;
long long card[MAX_N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> numCard;
for (int index = 1; index <= numCard; index++) {
cin >> card[index];
}
long long answer = 0;
for (int left = 1; left <= numCard; left++) {
for (int right = left; right <= numCard; right++) {
long long maxCard = -1e18, sum = 0;
for (int index = left; index <= right; index++) {
maxCard = max(maxCard, card[index]);
sum += card[index];
}
answer = max(answer, sum - maxCard);
}
}
cout << answer;
return 0;
}
Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{3}\).
Tutorial
Để tối ưu subtask 1, ta tận dụng việc duyệt các đoạn con để tìm max và tổng, Nhờ đó, ta không cần phải duyệt thêm \(\mathcal{O}(n)\) để tính.
Độ phức tạp: \(\mathcal{O}(n^{2})\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
int numCard;
long long card[MAX_N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> numCard;
for (int index = 1; index <= numCard; ++index) {
cin >> card[index];
}
long long answer = 0;
for (int left = 1; left <= numCard; ++left) {
long long mx = -1e18, sum = 0;
for (int right = left; right <= numCard; ++right) {
mx = max(mx, card[right]);
sum += card[right];
answer = max(answer, sum - mx);
}
}
cout << answer;
return 0;
}
Subtask \(3\) (\(30\%\) số điểm): \(|a_{i}| \leq 10^{2}\).
Tutorial
Gọi \(dp[i][mx]\) là đoạn con có tổng lớn nhất kết thúc ở \(i\) và có max là \(mx\). Khi đó, ta chuyển trạng thái như sau:
- Nếu thêm phần tử mới vào đoạn con hiện tại: \(dp[i + 1][\max(mx, a[i + 1])] = \max(dp[i + 1][\max(mx, a[i + 1])] , dp[i][mx] + a[i + 1])\)
- Nếu tạo đoạn con mới: \(dp[i + 1][a[i + 1]] = \max(dp[i + 1][a[i + 1]], a[i + 1])\)
Kết quả bài toán sẽ là \(\max(dp[i][mx] - mx)\).
Độ phức tạp: \(\mathcal{O}(\max a_{i} \times n)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100005;
const int MAX = 205;
const int INF = 1e9;
int numCard;
int card[MAX_N];
int dp[MAX_N][MAX];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> numCard;
for (int index = 1; index <= numCard; ++index) {
cin >> card[index];
}
memset(dp, -0x3f, sizeof dp);
dp[0][100] = 0;
for (int index = 0; index < numCard; ++index) {
for (int mx = 0; mx < MAX; ++mx) {
if (dp[index][mx] > -INF) {
dp[index + 1][max(mx, card[index + 1] + 100)] = max(
dp[index + 1][max(mx, card[index + 1] + 100)], dp[index][mx] + card[index + 1]);
dp[index + 1][card[index + 1] + 100] =
max(dp[index + 1][card[index + 1] + 100], card[index + 1]);
}
}
}
int answer = 0;
for (int index = 1; index <= numCard; ++index) {
for (int mx = 0; mx < MAX; ++mx) {
answer = max(answer, dp[index][mx] - (mx - 100));
}
}
cout << answer;
return 0;
}
Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Nhận xét: Để Tí tối thiểu tổng sau khi bỏ một phần tử ra khỏi đoạn con, Tí sẽ luôn chọn phần tử có giá trị lớn nhất trong đoạn. Còn Tèo sẽ cố gắng chọn đoạn sao cho tổng được tối đa.
Với \(1 \leq i \leq n\), giả sử \(a_{i}\) là phần tử mà Tí sẽ bỏ ra. Khi đó, Tèo cần chọn một đoạn con sao cho \(x \leq i \leq y\), \(a_{i} > a_{j} \, \forall x \leq j \leq y\) và \(sum[x \dots y]\) là lớn nhất.
Để tối đa tổng, ta cần tối đa từng đoạn \(sum[x \dots i]\) và \(sum[i \dots y]\). Để tìm \(x\), ta xác định vị trí \(L[i]\) nhỏ nhất sao cho \(a_{j} < a_{i} \,\forall L[i] \leq j \leq i\). Ta biết \(sum[x \dots i] = sum[1 \dots i] - sum[1 \dots x - 1]\), do đó \(x\) phải là vị trí sao cho \(L[i] - 1 \leq x \leq i - 1\) và \(sum[1\dots x-1]\) đạt giả trị nhỏ nhất.
Ta giải quyết hai phần của tổng \(sum[x \dots y]\) một cách độc lập. Để xác định \(L[i]\), ta dùng kĩ thuật deque min-max để xác định toàn bộ \(L[i]\) trong \(\mathcal{O}(n)\). Sau đó tìm \(x\) tương ứng cho mỗi \(i\) bằng cách duy trì một cây Fenwick Tree hoặc cây Segment Tree trong \(\mathcal{O}(\log_{2} n)\). Ta cũng làm tương tự với \(y\).
Sau khi hoàn tất, ta chọn vị trí \(i\) có tổng lớn nhất.
Độ phức tạp: \(\mathcal{O}(n \log_{2} n)\).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5;
const long long INF = 1e18;
struct FenwickTree {
int treeSize;
vector<long long> nodes;
void init(int treeSize) {
this->treeSize = treeSize;
nodes.assign(treeSize + 1, INF);
}
void update(int id, long long val) {
for (; id <= treeSize; id += (id & -id)) {
nodes[id] = min(nodes[id], val);
}
}
long long get(int id) {
long long result = INF;
for (; id >= 1; id -= (id & -id)) {
result = min(result, nodes[id]);
}
return result;
}
};
int numCard;
long long lef[MAX_N], rig[MAX_N];
int card[MAX_N];
stack<int> st;
FenwickTree fenwickTree;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> numCard;
for (int index = 1; index <= numCard; ++index) {
cin >> card[index];
}
long long prefixSum = 0;
fenwickTree.init(numCard + 1);
fenwickTree.update(numCard + 1, 0);
for (int index = 1; index <= numCard; ++index) {
while (!st.empty() && card[st.top()] <= card[index]) {
st.pop();
}
int leftBound = st.empty() ? 1 : st.top() + 1;
lef[index] = prefixSum - fenwickTree.get(numCard - leftBound + 2);
prefixSum += card[index];
fenwickTree.update(numCard - index + 1, prefixSum);
st.push(index);
}
while (!st.empty()) {
st.pop();
}
long long suffixSum = 0;
fenwickTree.init(numCard + 2);
fenwickTree.update(numCard + 2, 0);
for (int index = numCard; index >= 1; --index) {
while (!st.empty() && card[st.top()] <= card[index]) {
st.pop();
}
int rightBound = st.empty() ? numCard : st.top() - 1;
rig[index] = suffixSum - fenwickTree.get(rightBound + 2);
suffixSum += card[index];
fenwickTree.update(index + 1, suffixSum);
st.push(index);
}
long long answer = -INF;
for (int index = 1; index <= numCard; ++index) {
answer = max(answer, lef[index] + rig[index]);
}
cout << answer;
return 0;
}
Bình luận