传送门
Luogu
解题思路
( ext{DP}) 很显然:
设 (dp_i) 表示前 (i) 个玩具的最小费用,转移就是:
(dp_i = maxlimits_{0le j < i}left{dp_j+(i-j-1+s_i-s_j-L)^2
ight})
(s_i=sum_{j=1}^ic_j),但这是 (O(n^2)) 的,显然不够优秀,考虑进一步优化。
我们可以化简一下这个式子:
假设 (dp_i) 成功从 (dp_j) 转移过来,那么就有:
(dp_i=dp_j+(i-j-1+s_i-s_j-L)^2)
整理一下式子:
设 (a_i = s_i+i-L-1,b_i=s_i+i)
那么就有:
(dp_i=dp_j+(a_i-b_j)^2)
展开并移项可得:
(dp_j+b_j^2=2a_ib_j+dp_i-a_i^2)
再设 (x_i=2b_i,y_i=dp_i+b_i^2)
(y_j=a_ix_j+dp_i-a_i^2)
又因为 (a_i^2) 是定值,要最小化 (dp_i) ,那么就相当于坐标系中一条斜率为 (a_i) 的经过点 ((x_j, y_j)) ,使得它的纵截距最小化。
又因为我们的 (a_i, b_i) 都是递增的,显然这些可能的转移点都要在下凸壳上才能使截距最小。
所以我们用单调队列,维护一下凸包上的转移点。
当前最优转移点从队头不断弹出不最优的点,并用最后的合法情况转移 (dp_i)。
插入当前的 (i) 时,为了确保凸包的性质,先不断从队尾弹出不合法的点,再插入 (i)。
最后输出答案 (dp_n)。
细节注意事项
- 咕咕咕
参考代码
#include <algorithm>
#include <iostream>
#include <cstdio>
#define rg register
using namespace std;
typedef double db;
const int _ = 50010;
int n, L; db dp[_], s[_], A[_], B[_];
int hd = 1, tl = 1, Q[_];
inline db X(int i) { return (db) B[i]; }
inline db Y(int i) { return (db) dp[i] + B[i] * B[i]; }
inline db slope(int i, int j) { return (db) (Y(j) - Y(i)) / (X(j) - X(i)); }
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
scanf("%d%d", &n, &L);
for (rg int i = 1; i <= n; ++i) scanf("%lf", s + i), s[i] += s[i - 1];
for (rg int i = 1; i <= n; ++i) A[i] = (db) s[i] + i - L - 1;
for (rg int i = 1; i <= n; ++i) B[i] = (db) s[i] + i;
for (rg int i = 1; i <= n; ++i) {
while (hd < tl && slope(Q[hd], Q[hd + 1]) < 2 * A[i]) ++hd;
dp[i] = dp[Q[hd]] + (A[i] - B[Q[hd]]) * (A[i] - B[Q[hd]]);
while (hd < tl && slope(Q[tl - 1], Q[tl]) > slope(Q[tl - 1], i)) --tl;
Q[++tl] = i;
}
printf("%lld
", (long long) dp[n]);
return 0;
}
完结撒花 (qwq)