## Bài toán yêu cầu bạn tìm độ đẹp tốt nhất khi chọn $k$ tấm gỗ, lấy một tấm gỗ làm cửa với độ đẹp $B_i$ và còn lại làm rào với độ đẹp $A_i$.
## Một hướng giải là ưu tiên chọn những tấm gỗ có $A_i$ tốt nhất làm rào, sau đó điều chỉnh cách chọn để tìm tấm gỗ với $B_i$ phù hợp làm cửa. Có thể giải như sau:
- Bạn sắp xếp các tấm gỗ giảm dần theo $A_i$, rồi theo $B_i$, sẽ thuận lợi trong việc tìm đáp án.
- Để ý bài toán -- Vì bạn chỉ cần một tấm gỗ làm cửa, nên bạn "tham lam" những độ đẹp tốt nhất cho hàng rào đến khi cần phải làm cửa. Từ đó, bạn sẽ có hai cách để tìm:
$1.$ Chọn ra $k$ tấm gỗ tốt nhất đầu tiên làm rào, sau đó trong những tấm ấy chọn ra một tấm làm cửa.
$2.$ Chọn ra $k - 1$ tấm gỗ tốt nhất đầu tiên làm rào, sau đó chọn ra một trong những tấm còn lại (từ tấm thứ $k$ trở đi) làm cửa.
- Với tư tưởng này, bạn khởi tạo hai mảng:
- $f[i]$, là lượng thay đổi độ đẹp khi chọn một trong $i$ tấm gỗ đầu tiên làm cửa:
\begin{equation}
f[i] = max(f[i - 1], B[i] - A[i]).
\end{equation}
- $g[i]$, là độ đẹp tốt nhất khi chọn một trong các tấm gỗ từ $i$ đến $n$ làm cửa:
\begin{equation}
g[i] = max(g[i + 1], B[i]).
\end{equation}
- Bạn chọn ra $k$ tấm gỗ đầu tiên, và so sánh hai cách: một là thay đổi một tấm trong $k$ tấm đã chọn làm cửa, hai là bỏ tấm cuối cùng và tìm tấm khác làm cửa. Cách nào cho độ đẹp tốt hơn sẽ là đáp án.
### Code tham khảo:
```
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int LIM = 1e5 + 5;
const int BND = 1e9 + 9;
int n;
pair <int, int> shelf[LIM];
int f[LIM], g[LIM];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> shelf[i].first;
for (int i = 1; i <= n; ++i) cin >> shelf[i].second;
sort(shelf + 1, shelf + n + 1, greater<pair <int, int>>());
f[0] = LIM;
g[n + 1] = LIM;
for (int i = 1; i <= n; ++i) f[i] = max(f[i - 1], shelf[i].second - shelf[i].first);
for (int i = n; i >= 1; --i) g[i] = max(g[i + 1], shelf[i].second);
int acc = 0;
for (int k = 1; k <= n; ++k) {
if (k != 1) cout << ' ';
acc += shelf[k].first;
cout << max(acc + f[k], acc - shelf[k].first + g[k]);
}
}
```
noice
Created at
2 likes