专栏文章

CF 280E Sequence Transformation

rrizynvu
CF280E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miowkcsm
此快照首次捕获于
2025/12/03 02:19
3 个月前
此快照最后确认于
2025/12/03 02:19
3 个月前
查看原文
cnblogs。
只会复读其他题解了/ll。
首先有一个 dp 是记 fi,jf_{i, j} 表示 yi=jy_i = j 时的最小代价，转移形如 fi,j=min⁡j−b≤k≤j−a{fi−1,k}+(j−xi)2f_{i, j} = \min\limits_{j - b\le k\le j - a} \{f_{i - 1, k}\} + (j - x_i)^2。
不过此时遇到的问题是 jj 的上界不仅很大而且可能为小数，是十分不好维护的。
此时一个很妙的想法是考虑把 fif_i 当作是一个关于 jj 的函数，即看作 fi(j)f_i(j)。
这个函数可能会有一些分段的情况，但是首先对这个取 min⁡\min 的操作感受一下，段数其实并不多。
于是考虑分段维护 fi′(j)f_i'(j)，这样的好处将会在后文体现。
首先来考虑初值：f1(j)=(j−x1)2f_1(j) = (j - x_1)^2，那么有 f1′(j)=2(j−x1)f_1'(j) = 2(j - x_1)。
然后来考虑第一次转移：f2,j=min⁡j−b≤k≤j−a{f1,k}+(j−x2)2f_{2, j} = \min\limits_{j - b\le k\le j - a} \{f_{1, k}\} + (j - x_2)^2。
先来考虑简化这个 min⁡j−b≤k≤j−a{f1,k}\min\limits_{j - b\le k\le j - a} \{f_{1, k}\}， f1(j)f_1(j) 是具有性质的，这是单调递增的，所以考虑找到使 f1(j)f_1(j) 取到最小值的 k=x1k = x_1，那么 min⁡j−b≤k≤j−a{f1,k}={f1(k)k+a≤j≤k+bf1(j−a)j<k+af1(j−b)j>k+b\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⁡j−b≤k≤j−ag(j) = \min\limits_{j - b\le k\le j - a} ，那么会发现 g′(j)={0k+a<j<k+bf1′(j−a)j<k+af1′(j−b)j>k+bg'(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)g'(j) 也是单调不降的。
那么 f2(j)=g(j)+(j−x2)2f_2(j) = g(j) + (j- x_2)^2，所以 f2′(j)=g′(j)+2(j−x2)f_2'(j) = g'(j) + 2(j - x_2)，会发现这依然是不降的。
于是可以发现，这之后的每一步转移也是类似的，都可以说明 fi′(j)f_i'(j) 其实是单调不降的。
那么每次转移都可以考虑求出使得取到 fi(j)f_i(j) 的最小值的值 kk，这是容易通过 fi′(j)f'_i(j) 来发现的。
于是只需要把 fi′(j)f_i'(j) 从 kk 处劈开，左边平移 aa 位，右边平移 bb 位，并把 (k+a,k+b)(k + a, k + b) 都填充上 00，最后再加上 2(j−xi+1)2(j - x_{i + 1}) 这个函数，就实现了 fi′(j)→fi+1′(j)f_i'(j)\to f_{i + 1}'(j) 的转移。
需要注意的是 fi′(j)f_i'(j) 并不一定是连续的，通常 kk 会满足 fi′(k)=0f_i'(k) = 0，但是在定义域限制下可能并不能找到合适的 kk，但此时 kk 一定会在端点 / 分界点处（满足左侧 fi′(k)<0f_i'(k) < 0，右侧 fi′(k)>0f'_i(k) > 0，不过端点处可能还需要一些特判）。
于是每一步转移都可以 O(n)\mathcal{O}(n) 完成，总的复杂度就为 O(n2)\mathcal{O}(n^2)。
对于实现，可以考虑维护分界点的点值 (pi,j,fi,j)(p_{i, j}, f_{i, j})，这样更容易处理平移的问题，因为 fi′(j)f'_{i}(j) 是一次函数，所以分界点之间的 fi′(j)f_i'(j) 是容易表示出来的。
由于这种做法的空间并不是十分友好，点值需要滚掉，可以考虑记下每一个点值是 33 种情况的哪一种得到的，在构造时倒推，具体可以见实现。
还有就是，建议用 long double。
C
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...