CF 280E Sequence Transformation

rizynvu · 2025-07-13 21:04:09 · 题解

cnblogs。

只会复读其他题解了/ll。

首先有一个 dp 是记 f_{i, j} 表示 y_i = j 时的最小代价，转移形如 f_{i, j} = \min\limits_{j - b\le k\le j - a} \{f_{i - 1, k}\} + (j - x_i)^2。

不过此时遇到的问题是 j 的上界不仅很大而且可能为小数，是十分不好维护的。

此时一个很妙的想法是考虑把 f_i 当作是一个关于 j 的函数，即看作 f_i(j)。
这个函数可能会有一些分段的情况，但是首先对这个取 \min 的操作感受一下，段数其实并不多。

于是考虑分段维护 f_i'(j)，这样的好处将会在后文体现。

首先来考虑初值：f_1(j) = (j - x_1)^2，那么有 f_1'(j) = 2(j - x_1)。

然后来考虑第一次转移：f_{2, j} = \min\limits_{j - b\le k\le j - a} \{f_{1, k}\} + (j - x_2)^2。

先来考虑简化这个 \min\limits_{j - b\le k\le j - a} \{f_{1, k}\}， f_1(j) 是具有性质的，这是单调递增的，所以考虑找到使 f_1(j) 取到最小值的 k = x_1，那么 \min\limits_{j - b\le k\le j - a} \{f_{1, k}\} = \begin{cases}f_1(k) &k + a\le j\le k + b\\ f_1(j - a) & j < k + a\\ f_1(j - b) & j > k + b\end{cases}。
令 g(j) = \min\limits_{j - b\le k\le j - a} ，那么会发现 g'(j) = \begin{cases} 0 & k + a < j < k + b\\ f_1'(j - a) & j < k + a\\ f_1'(j - b) & j > k + b\end{cases}，即 g'(j) 也是单调不降的。

那么 f_2(j) = g(j) + (j- x_2)^2，所以 f_2'(j) = g'(j) + 2(j - x_2)，会发现这依然是不降的。

于是可以发现，这之后的每一步转移也是类似的，都可以说明 f_i'(j) 其实是单调不降的。

那么每次转移都可以考虑求出使得取到 f_i(j) 的最小值的值 k，这是容易通过 f'_i(j) 来发现的。
于是只需要把 f_i'(j) 从 k 处劈开，左边平移 a 位，右边平移 b 位，并把 (k + a, k + b) 都填充上 0，最后再加上 2(j - x_{i + 1}) 这个函数，就实现了 f_i'(j)\to f_{i + 1}'(j) 的转移。

需要注意的是 f_i'(j) 并不一定是连续的，通常 k 会满足 f_i'(k) = 0，但是在定义域限制下可能并不能找到合适的 k，但此时 k 一定会在端点 / 分界点处（满足左侧 f_i'(k) < 0，右侧 f'_i(k) > 0，不过端点处可能还需要一些特判）。

于是每一步转移都可以 \mathcal{O}(n) 完成，总的复杂度就为 \mathcal{O}(n^2)。

对于实现，可以考虑维护分界点的点值 (p_{i, j}, f_{i, j})，这样更容易处理平移的问题，因为 f'_{i}(j) 是一次函数，所以分界点之间的 f_i'(j) 是容易表示出来的。

由于这种做法的空间并不是十分友好，点值需要滚掉，可以考虑记下每一个点值是 3 种情况的哪一种得到的，在构造时倒推，具体可以见实现。

还有就是，建议用 long double。

#include <bits/stdc++.h>

#define double long double

constexpr double eps = 1e-9;

constexpr int maxn = 6000 + 10;

int n, m, x[maxn], a, b;

double p[maxn * 2], f[maxn * 2];

double pu[maxn];
char lst[maxn][maxn * 2];

double y[maxn];

int main() {
    scanf("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 1; i <= n; i++) scanf("%d", &x[i]);

    p[1] = 1.0, f[1] = 2.0 * (p[1] - x[1]);
    p[2] = m, f[2] = 2.0 * (p[2] - x[1]);

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= (i - 1) * 2; j++) {
            if ((j == 0 || f[j] < eps) && (j == (i - 1) * 2 || -eps < f[j + 1])) {
                if (p[j + 1] - p[j] > eps && 1 <= j && j < (i - 1) * 2) {
                    pu[i - 1] = p[j] + (-f[j]) * (p[j + 1] - p[j]) / (f[j + 1] - f[j]);
                } else if (j >= 1) {
                    pu[i - 1] = p[j];
                } else {
                    pu[i - 1] = p[1];
                }
                for (int k = (i - 1) * 2; k >= j + 1; k--) {
                    p[k + 2] = p[k] + b, f[k + 2] = f[k], lst[i][k + 2] = 2;
                }
                p[j + 1] = pu[i - 1] + a, f[j + 1] = 0, lst[i][j + 1] = 1;
                p[j + 2] = pu[i - 1] + b, f[j + 2] = 0, lst[i][j + 2] = 1;
                for (int k = 1; k <= j; k++) {
                    p[k] += a, lst[i][k] = 0;
                }
                break;
            }
        }

        for (int j = 1; j <= i * 2; j++) {
            f[j] += 2.0 * (p[j] - x[i]);
        }
    }

    const int low = 1 + a * (n - 1), upp = m;
    double val = -1;
    for (int i = 0; i <= n * 2; i++) {
        if ((i == 0 || f[i] < eps) && (i == n * 2 || -eps < f[i + 1])) {
            double u;
            if (p[i + 1] - p[i] > eps && 1 <= i && i < 2 * n) {
                u = p[i] + (-f[i]) * (p[i + 1] - p[i]) / (f[i + 1] - f[i]);
            } else if (i >= 1) {
                u = p[i];
            } else {
                u = p[1];
            }
            if (low - eps < u && u < upp + eps) {
                val = u;
            } else if (u < low + eps) {
                val = low;
            } else {
                val = upp;
            }
        }
    }

    y[n] = val;
    for (int i = n; i > 1; ) {
        for (int j = 1; j < i * 2; j++) {
            if (p[j] - eps < val && val < p[j + 1] + eps) {
                if (lst[i][j] == 1 && lst[i][j + 1] == 1) {
                    val = pu[i - 1];
                } else if (lst[i][j] == 0) {
                    val -= a;
                } else {
                    val -= b;
                }
            }
        }
        for (int j = 1; j <= i * 2; j++) {
            if (lst[i][j] == 0) {
                p[j] -= a;
            }
            if (lst[i][j] == 2) {
                p[j - 2] = p[j] - b;
            }
        }
        y[--i] = val;
    }

    double ans = 0;
    for (int i = 1; i <= n; i++) {
        printf("%.10Lf ", y[i]);
        ans += (y[i] - x[i]) * (y[i] - x[i]);
    }
    printf("\n%.10Lf\n", ans);
    return 0;
}