求助关于斜优后 dp_i 的计算
查看原帖
求助关于斜优后 dp_i 的计算
1378591
Barewalk楼主2025/7/27 22:31

下面的代码是正确的,而注释掉的部分是错误的,不知道两者有什么区别。

#include <bits/stdc++.h>
using ll = long long;
constexpr int MAXN = 5e4 + 5, P = 1e9 + 7;
using namespace std;
int n, L;
int l, r, q[MAXN];
double a[MAXN], b[MAXN], dp[MAXN];
double x(int i) {return b[i];}
double y(int i) {return dp[i] + b[i] * b[i];}
double slope(int i, int j) {return (y(i) - y(j)) / (x(i) - x(j));}
int main() {
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin >> n >> L;
	b[0] = L + 1;
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
		a[i] += a[i - 1] + 1, b[i] = a[i] + L + 1;
	}
	for (int i = 1; i <= n; ++ i) {
		while (l < r && slope(q[l], q[l + 1]) < 2 * a[i]) l ++;
		// dp[i] = y(q[l]) - 2 * a[i] * x(q[l]) + a[i] * a[i];
		dp[i] = dp[q[l]] + (a[i] - b[q[l]]) * (a[i] - b[q[l]]);
		while (l < r && slope(q[r - 1], q[r]) > slope(q[r - 1], i)) r --;
		q[++ r] = i; 
	}
	cout << (ll)dp[n] << '\n';
	return 0;
}
2025/7/27 22:31
加载中...