1 条题解
-
0
[Z] Frog 3(dp_z)题解
题意简述
块石头高度严格递增。青蛙从 出发,可跳到任意更靠右的石头 ,代价 。求到达 的最小总代价。
思路
朴素 DP
$$f_j = \min_{i<j}\left( f_i + (h_j-h_i)^2 + C \right).$$在 时不可行。
斜率优化
把式子展开:
$$f_j = h_j^2 + C + \min_{i<j}\left( f_i + h_i^2 - 2h_i h_j \right).$$把每个 看成一条直线
$$y = m_i x + b_i,\qquad m_i = -2h_i,\quad b_i = f_i + h_i^2 + C,$$则 —— 查询一组直线在 处的最小值。
单调性
- 严格递增 ⇒ 斜率 严格递减;
- 询问的 也严格递增。
两者都单调 ⇒ 用一个单调队列维护下凸壳:队头弹出不再最优的直线,队尾维护凸性,每次 摊还。
整数运算
可达约 , 项也在此量级,本解全部用
long long整数 +__int128判叉积,避免浮点误差。复杂度
时间 ,空间 。
参考代码
#include <cstdio> using namespace std; typedef long long ll; typedef __int128 lll; int main() { int n; ll C; scanf("%d %lld", &n, &C); static ll h[200005], S[200005], B[200005], f[200005]; for (int i = 1; i <= n; i++) scanf("%lld", &h[i]); int head = 0, tail = 0; f[1] = 0; // 转成求最大值:y = s_i * x + c_i, s_i = 2h_i, c_i = -(f_i + h_i^2 + C) S[tail] = 2 * h[1]; B[tail] = -(f[1] + h[1] * h[1] + C); tail++; for (int j = 2; j <= n; j++) { while (head + 1 < tail && S[head] * h[j] + B[head] <= S[head + 1] * h[j] + B[head + 1]) head++; f[j] = h[j] * h[j] - (S[head] * h[j] + B[head]); ll s = 2 * h[j], c = -(f[j] + h[j] * h[j] + C); while (tail - head >= 2) { ll s1 = S[tail - 2], c1 = B[tail - 2], s2 = S[tail - 1], c2 = B[tail - 1]; if ((lll)(s - s2) * (c1 - c2) >= (lll)(c2 - c) * (s2 - s1)) tail--; else break; } S[tail] = s; B[tail] = c; tail++; } printf("%lld\n", f[n]); return 0; }易错点
- 代价是 , 是每次跳跃都加的,不是只加一次。
- 斜率与询问都单调时才能用单调队列;若 非递增就需用 Li Chao 树或二分。
- 叉积要用
__int128,long long相乘会溢出(、 量级)。 - 答案超过
int(样例 2 是 ),必须long long;若用浮点会丢精度,别用double。
数据说明
共 16 组:3 组官方样例(含 ); 极值( 跨度 、 → 保证答案超 int64 需
long long);;; 随机; 随机; 的等差 、随机 、含端点 与 的随机 、 随机。
- 1
信息
- ID
- 35
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者