可爱小萌新初学者代码求调!(玄关)
查看原帖
可爱小萌新初学者代码求调!(玄关)
1788032
BlackHoles楼主2025/8/1 10:31

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.

2025/8/1 10:31
加载中...