这题推式子略微需要一点手法。
你说得对,但这如果真的是 HNOI2008 的赛场,那真的赚麻了。
$O(n^2)$ DP 能干上 50pts??数据有待减弱是吧。
朴素 DP 显然是简单的。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 15;
int n, L, c[N];
long long dp[N], s[N];
long long pw(long long x) { return x * x; }
int main() {
scanf("%d%d", &n, &L);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]), s[i] = s[i - 1] + c[i];
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
dp[i] = min(dp[i], dp[j] + pw(i - j - 1 + s[i] - s[j] - L));
}
}
printf("%lld\n", dp[n]);
return 0;
}
然后试图暴力展开,发现有整整 $36$ 项,遂破防。
然后试图设 $p_j = i - j - 1, q_j = s_i - s_j$,推了一会儿发现不太对劲,还是要展开。
于是考虑转而把下标相同的信息合并:
设 $a_i = s_i + i$,$b_i = s_i + i + L + 1$,则转移方程可以化简为:
$$f_i = \min\limits_{j=0}^{i-1} \{ f_j + (a_i - b_j)^2 \}$$
这下爽了,式子简单到可以爆推。
按照常规套路推出:
$$\frac{(f_{j_1} + b_{j_1}^2) - (f_{j_2} + b_{j_2}^2)}{b_{j_1} - b{j_2}} \geq 2a_{i}$$
其中 $a,b,b^2$ 都是常数,由于是取 $\min$ 要维护下凸壳。
然后发现右侧的 $2a_{i}$ 显然是一个单调递增的形式,所以只需要维护队头即可。
感觉斜率优化真的很好写。
但是推式子之前要注意一下能不能化成可以斜优的形式。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 15;
int n, L, c[N];
long long dp[N], s[N], a[N], b[N];
int q[N], st, ed;
long long X(int p) { return b[p]; }
long long Y(int p) { return dp[p] + b[p] * b[p]; }
double slope(int a, int b) {
if (X(a) == X(b)) {
if (Y(a) == Y(b)) return 0;
if (Y(a) > Y(b)) return -1e18;
else return 1e18;
}
return (Y(a) - Y(b)) * 1.00 / (X(a) - X(b));
}
int main() {
scanf("%d%d", &n, &L);
for (int i = 1; i <= n; i++) scanf("%d", &c[i]), s[i] = s[i - 1] + c[i];
for (int i = 0; i <= n; i++) a[i] = s[i] + i, b[i] = s[i] + i + L + 1;
st = ed = 1; q[1] = 0;
for (int i = 1; i <= n; i++) {
while (st < ed && slope(q[st], q[st + 1]) <= 2 * a[i]) st++;
int j = q[st];
dp[i] = dp[j] + (a[i] - b[j]) * (a[i] - b[j]);
while (st < ed && slope(q[ed - 1], q[ed]) >= slope(q[ed], i)) ed--;
q[++ed] = i;
}
printf("%lld\n", dp[n]);
return 0;
}