Hướng dẫn giải của Thi thử HSG9 2026 - Ngày 4 - Perman
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Ta nhận thấy rằng, nếu số lượng đoạn được cho phép (~k~) càng lớn thì ta có thể chọn càng tối ưu, do đó, nếu gọi ~f(x)~ là kết quả nếu ~k = x~ thì ~\forall x\leq x:\ f(x)\leq f(x')'~. Điều này dẫn ta tới với suy nghĩ: liệu có thể sử dụng WQS DP được cho bài toán này không ?
Đáp án là có, và tính chất của nó được biểu diễn qua hàm sau:
- Gọi ~g(x)~ = ~f(x + 2) - f(x)~.
- ~\forall x\leq x',\ x\equiv x'\ (mod\ 2):\ g(x)\geq g(x')~.
Lí do cho điều này chính là nếu như ta xét một mô hình dãy thì nó sẽ có dạng như sau:
- Ban đầu, ta cho một dãy ~b~ có dạng ~b = [1,\ -1,\ 1,\ -1,\ ...]~.
- Nếu ta xét một đoạn con ~(l,\ r)~ mà ~\sum^{r}_{i = l} a_i\times b_i < \sum^{r}_{i = l} -a_i\times b_i~ thì ta có thể thực hiện chia dãy ở hai vị trí ~l~ và ~r + 1~ để đổi dấu của đoạn con đó nhằm nhận được chênh lệch (vì điều này nên ta mới xét ở ~f(x)~ và ~f(x + 2)~).
- Bằng logic đó, ta cũng có thể nhận xét là ta nên ưu tiên những đoạn có chênh lệch lớn thì đảo dấu trước, do đó phần chênh lệch của các lần lật sau sẽ bé hơn, từ đó ta thỏa mãn được tính chất cần để có thể dùng WQS DP.
P/S: Với bài toán này, rất nhiều thí sinh đã sử dụng thuật toán Alien Trick (hay WQS DP) nhưng do xét thiếu điều kiện ~x\equiv x'\ (mod\ 2)~ nên đều không thành công.
Code mẫu:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
const ll inf = 1e18;
int n, k, a[N];
pair<ll, int> dp[N][2][2];
tuple<ll, int, ll, int> alien (const ll &penalty){
for (int i = 0; i <= n; ++i){
for (int j = 0; j <= 1; ++j){
for (int l = 0; l <= 1; ++l){
dp[i][j][l] = {-inf, -N};
}
}
}
dp[1][0][0] = {a[1] - penalty, 1};
for (int i = 2; i <= n; ++i){
pair<ll, int> m1 = max(dp[i - 1][0][0], dp[i - 1][0][1]);
pair<ll, int> m2 = max(dp[i - 1][1][0], dp[i - 1][1][1]);
dp[i][0][0] = max(make_pair(dp[i - 1][0][1].first + 1ll * a[i], dp[i - 1][0][1].second), make_pair(m2.first + 1ll * a[i] - penalty, m2.second + 1));
dp[i][0][1] = {dp[i - 1][0][0].first - 1ll * a[i], dp[i - 1][0][0].second};
dp[i][1][0] = max(make_pair(dp[i - 1][1][1].first + 1ll * a[i], dp[i - 1][1][1].second), make_pair(m1.first + 1ll * a[i] - penalty, m1.second + 1));
dp[i][1][1] = {dp[i - 1][1][0].first - 1ll * a[i], dp[i - 1][1][0].second};
}
pair<ll, int> m1 = max(dp[n][0][0], dp[n][0][1]);
pair<ll, int> m2 = max(dp[n][1][0], dp[n][1][1]);
return make_tuple(m1.first, m1.second, m2.first, m2.second);
}
int32_t main (){
const string task = "per";
freopen ((task + ".inp").c_str(), "r", stdin);
freopen ((task + ".out").c_str(), "w", stdout);
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i){
scanf("%d", &a[i]);
}
ll l = 0, r = 1e16, opt = 1e16;
while (l <= r){
ll m = (l + r) >> 1;
const auto &[f1, g1, f2, g2] = alien(m);
if (k & 1){
if (g1 >= k){
opt = m;
l = m + 1;
} else {
r = m - 1;
}
} else {
if (g2 >= k){
opt = m;
l = m + 1;
} else {
r = m - 1;
}
}
}
const auto &[f1, g1, f2, g2] = alien(opt);
if (k & 1){
printf("%lld", f1 + 1ll * k * opt);
} else {
printf("%lld", f2 + 1ll * k * opt);
}
return 0;
}
Bình luận