WA on #1, #9, #10, #11,下不了测试点。
// 参考题解区高效做法。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 40000;
const ll INF = 1e18;
int n, a[N], ar[N];
int f[N], len, res, b[N]; // 1.使用 DP 数组。
vector <int> vec[N]; // vec[a] 记录以 i 结尾最长不下降子序列长度为 a 的 i。
ll dp[N]; // 幅度 DP 数组。
ll suml[N], sumr[N]; // 前缀和数组。
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
ar[i] = a[i] - i;
}
ar[0] = INT_MIN, ar[++n] = INT_MAX; // 补充一个极大值。
// 1.求 ar 的最长不下降子序列。
f[++len] = ar[0];
b[0] = 1;
vec[1].push_back(0);
for (int i = 1; i <= n; ++i) {
if (ar[i] >= f[len]) {
f[++len] = ar[i];
b[i] = len;
vec[len].push_back(i);
}
else {
// 二分寻找最佳位置。
int l = 0, r = len, mid, pos;
while (l <= r) {
mid = (l + r) >> 1;
if (f[mid] <= ar[i]) {
pos = mid;
l = mid + 1;
}
else
r = mid - 1;
}
++pos; // pos 为以 i 结尾的最长上升子序列的长度。
f[pos] = ar[i];
b[i] = pos;
vec[pos].push_back(i);
}
}
--len;
// len 为最多保留的数的个数。
res = n - len;
cout << res << '\n';
for (int i = 1; i <= n; ++i)
dp[i] = INF;
for (int i = 1; i <= n; ++i) {
int length = b[i] - 1;
for (int j : vec[length]) { // 枚举决策转移点。
if (j > i || ar[j] > ar[i])
continue;
suml[j] = sumr[i] = 0;
for (int k = j + 1; k < i; ++k)
suml[k] = suml[k-1] + abs(ar[k] - ar[j]);
for (int k = i - 1; k > j; --k)
sumr[k] = sumr[k+1] + abs(ar[k] - ar[i]);
for (int k = j; k < i; ++k)
dp[i] = min(dp[i], dp[j] + suml[k] + sumr[k+1]);
}
}
cout << dp[n];
return 0;
}
Thx.