Hướng dẫn cho Sắp xếp hoán vị
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.
Subtask 1
Duyệt trạng thái \(9!\) để tìm kết quả tối ưu.
Subtask 2
Nhận xét: Trong các cách sắp xếp tối ưu các tập đoạn được chọn để sắp xếp là \(S\) thì với hai đoạn bất kì \([l_i, r_i]\) và \([l_j, r_j]\) thì giao của hai đoạn này là rỗng.
Do đó ta có thể quy hoạch động. Gọi \(dp_i\) là chi phí nhỏ nhất để sort từ \(1\) đến \(i\), các vị trí \(i\) phải thỏa mãn \(max(a_1, a_2, ..., a_i) = i\).
Từ đó: \(dp_i = min(dp_j + \lfloor \sqrt{i - j} \rfloor)\) với \(j\) thỏa mãn \(max(a_1, a_2, ..., a_j) = j\).
Độ phức tạp: \(\mathcal{O}(N^2)\).
Subtask 3
Nhận xét:
- Với dãy độ dài \(n\), chi phí tối đa để sắp xếp lại dãy là \(\lfloor \sqrt{N} \rfloor\) (chọn dãy \([1..N]\)).
- \(dp_i \geq dp_j\) với \(i \geq j\).
Từ đó, với mỗi \(i\), ta chỉ cần quan tâm tối đa \(\lfloor \sqrt{N} \rfloor\) vị trí \(j\) tương ứng \(\lfloor \sqrt{i - j} \rfloor = 1, 2, ..., \lfloor \sqrt{N} \rfloor\).
Với chi phí \(x\), ta cần tìm vị trí \(j\) nhỏ nhất thỏa mãn \(\lfloor \sqrt{i - j} \rfloor = x\).
\(\rightarrow\) \(i - (x + 1)^2 + 1 \le j \le i - x^2\)
Gọi \(p_k = j\) là vị trí nhỏ nhất lớn hơn hoặc bằng \(k\) thỏa mãn \(max(a_1, a_2, ..., a_j) = j\). Từ đó \(j = p_{max(0, i-(x+1)^2+1)}\). Cập nhật \(dp_i = dp_j + x\).
Độ phức tạp: \(\mathcal{O}(N\sqrt{N})\).
Subtask 4
Với nhận xét ở subtask 3, ta có thể sử dụng quy hoạch động đổi biến. Gọi:
- \(dp_x = i\) là vị trí \(i\) lớn nhất có thể sắp xếp tăng dần sử dụng \(x\) chi phí.
- \(m_i = j\) với \(j\) là giá trị lớn nhất tồn tại hoán vị \([1..j]\) trong đoạn \([1..i]\) của dãy \(a\).
Duyệt qua số chi phí từ \(1\) đến \(\lfloor \sqrt{N} \rfloor\) để tính \(dp_i\). Với chi phí \(j < i\) để tính kết quả cho chi phí \(i\), ta có thể sắp xếp tối đa đoạn từ \([dp_j + 1, min(n, dp_j + (i - j + 1)^2 - 1)]\). Đặt \(pos_j = min(n, dp_j + (i-j+1)^2-1)\), việc chọn sắp xếp đến \(pos_j\) luôn tối ưu bởi \(m_i \geq m_{i-1} \; \forall \; 1 \le i \le n\). Cập nhật \(dp_i=max(m_{pos_j})\).
Lưu ý: nếu \(m_{pos_j}=j\) (\(a[1..pos_j]\) là hoán vị từ \(1\) đến \(pos_j\)) và \(a_{pos_j+1}=pos_j+1, a_{pos_j+2}=pos_j+2, ..., a_{pos_j+k}=pos_j+k\) thì ta cần cập nhật lại \(dp_i=pos_j+k\).
Độ phức tạp: \(\mathcal{O}(\sqrt{N} \times \sqrt{N}) = \mathcal{O}(N)\)
Code C++ tham khảo (Sub 2, 3, 4)
/*
Tag:
*/
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())
using namespace std;
const int maxn = 1e6 + 5;
const int oo = 1e18;
int n, a[maxn];
int sqr[maxn];
void prep(){
for (int i = 1; i < maxn; i++){
sqr[i] = sqrtl(i);
}
}
namespace SUB2{
const int maxn = 2e3 + 5;
int dp[maxn];
int pre[maxn];
void solve(){
for (int i = 1; i <= n; i++){
pre[i] = max(pre[i - 1], a[i]);
}
for (int i = 1; i <= n; i++){
if (pre[i] != i){
dp[i] = oo;
continue;
}
dp[i] = oo;
if (pre[i - 1] == i - 1) dp[i] = dp[i - 1];
for (int j = i - 2; j >= 0; j--){
if (pre[j] == j){
dp[i] = min(dp[i], dp[j] + sqr[i - j]);
}
}
}
cout << dp[n] << endl;
}
}
namespace SUB3{
const int maxn = 1e6 + 5;
int dp[maxn];
int pre[maxn], p[maxn];
void solve(){
for (int i = 1; i <= n; i++){
pre[i] = max(pre[i - 1], a[i]);
}
int last = n + 1;
dp[n + 1] = oo;
for (int i = n; i >= 1; i--){
if (pre[i] == i) last = i;
p[i] = last;
}
for (int i = 1; i <= n; i++){
dp[i] = oo;
if (pre[i] != i){
continue;
}
if (pre[i - 1] == i - 1) dp[i] = dp[i - 1];
for (int x = 1; x <= sqr[n]; x++){
int j = max(0ll, i - (x + 1) * (x + 1) + 1);
dp[i] = min(dp[i], dp[p[j]] + x);
}
}
cout << dp[n] << endl;
}
}
namespace SUB4{
const int maxn = 1e6 + 5;
int dp[1005];
int m[maxn], lg[maxn];
bool check[maxn];
void solve(){
int ins = 1;
for (int i = 1; i <= n; i++){
check[a[i]] = true;
while (check[ins]){
++ins;
}
m[i] = ins - 1;
}
for (int i = n; i >= 1; i--){
lg[i] = lg[i + 1];
if (a[i] == i) lg[i]++;
else lg[i] = 0;
}
dp[0] = lg[1];
if (dp[0] == n){
cout << 0 << endl;
return;
}
for (int i = 1; i <= sqrt(n); i++){
for (int j = 0; j < i; j++){
int pos = min(n, dp[j] + (i - j + 1) * (i - j + 1) - 1);
dp[i] = max(dp[i], m[pos]);
if (m[pos] == pos){ // 1 -> pos là hoán vị
dp[i] = max(dp[i], m[pos] + lg[pos + 1]);
}
}
if (dp[i] == n){
cout << i << endl;
return;
}
}
}
}
void PROGRAM(int _){
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 2e3) SUB2::solve();
else if (n <= 1e5) SUB3::solve();
else
SUB4::solve();
}
signed main(){
freopen("SX.INP", "r", stdin);
freopen("SX.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
prep();
int test = 1;
for (int _ = 1; _ <= test; _++){
PROGRAM(_);
}
return 0;
}
Bình luận