题解：CF704B Ant Man

从这来的，套路都一样，预设型 DP。

把那个式子拆开，看每个数单独的贡献。

• 一个数比它左边的数小，它的贡献就是：\(-x_i + b_i\)
• 比它左边的数大，它的贡献就是：\(x_i + a_i\)
• 比它右边的数小，它的贡献就是：\(-x_i + d_i\)
• 比它右边的数大，它的贡献就是：\(x_i + c_i\)

即：

int Gl(int i) { // > 左边
    return x[i] + a[i];
}
int Gr(int i) { // > 右边
    return x[i] + c[i];
}
int Ll(int i) { // < 左边
    return -x[i] + b[i];
}
int Lr(int i) { // < 右边
    return -x[i] + d[i];
}

令 \(f_{i,j}\) 表示已经插入 \(i\) 个数，这些数构成了 \(j\) 个连续段。

新插入的数比后插入的数小，所以一个数插进去的时候可以直接根据前后有没有数来计算贡献。

分类讨论即可，我分的情况比较细致，其实有几个情况有重合，但胜在好理解。

如果 \(i=S\)：

• 插入到最左边，形成单独的块：
  • \(f_{i,j} = f_{i-1,j-1}+Lr(i)\)
• 插入到最左边块的左边。如果 \(E\) 已经插入，并且 \(j=1\)，这种情况就不成立了：
  • \(f_{i,j} = f_{i-1,j}+Gr(i)\)

如果 \(i=E\)：

• 插入到最右边，形成单独的块：
  • \(f_{i,j} = f_{i-1,j-1}+Ll(i)\)
• 插入到最右边块的右边。如果 \(S\) 已经插入，并且 \(j=1\)，这种情况不成立：
  • \(f_{i,j} = f_{i-1,j}+Gl(i)\)

接下来看平常的情况：

• 插入到所有数最左边，构成一个新块。如果 \(S\) 已经插入则不成立：
  • \(f_{i,j} = f_{i-1,j-1}+Ll(i)+Lr(i)\)
• 插入到最左边块的左边。如果 \(S\) 已经插入则不成立：
  • \(f_{i,j} = f_{i-1,j}+Ll(i)+Gr(i)\)
• 插入到所有数最右边，构成一个新块。如果 \(E\) 已经插入则不成立：
  • \(f_{i,j} = f_{i-1,j-1}+Ll(i)+Lr(i)\)
• 插入到最右边块的右边。如果 \(E\) 已经插入则不成立：
  • \(f_{i,j} = f_{i-1,j}+Gl(i)+Lr(i)\)
• 插到中间某块的左边。注意一定要有中间块，所以要满足 \(j>1\)：
  • \(f_{i,j} = f_{i-1,j}+Ll(i)+Gr(i)\)
• 插到中间某块的右边。注意一定要有中间块，所以要满足 \(j>1\)：
  • \(f_{i,j} = f_{i-1,j}+Gl(i)+Lr(i)\)
• 插到中间单独成块。两边一定要有块，所以要满足 \(j > 2\)：
  • \(f_{i,j} = f_{i-1,j-1}+Ll(i)+Lr(i)\)
• 插到中间链接两个块：
  • \(f_{i,j} = f_{i-1,j+1}+Gl(i)+Gr(i)\)

对于 DP 边界详细见代码。

代码用一些技巧合并了重复的情况。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxN = 5007;

int n, f[maxN][maxN];
int S, T;

int x[maxN], a[maxN], b[maxN], c[maxN], d[maxN];
int Gl(int i) {
    return x[i] + a[i];
}
int Gr(int i) {
    return x[i] + c[i];
}
int Ll(int i) {
    return -x[i] + b[i];
}
int Lr(int i) {
    return -x[i] + d[i];
}

int chkmin(int &x, int y) {
    return x = x > y ? y : x;
}

signed main() {
    cin >> n >> S >> T;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) cin >> d[i];

    memset(f, 0x3f, sizeof(f));
    if (S == 1)
        f[1][1] = Lr(1);
    else if (T == 1)
        f[1][1] = Ll(1);
    else
        f[1][1] = Ll(1) + Lr(1);
    for (int i = 2; i < n; i++) {
        for (int j = 1; j <= i; j++) {
            if (i == S || i == T) {
                if (i == S) {
                    chkmin(f[i][j], f[i - 1][j - 1] + Lr(i));
                    if (j > (i > T))
                        chkmin(f[i][j], f[i - 1][j] + Gr(i));
                }
                else {
                    chkmin(f[i][j], f[i - 1][j - 1] + Ll(i));
                    if (j > (i > S))
                        chkmin(f[i][j], f[i - 1][j] + Gl(i));
                }
                continue;
            }
            if (i > S && i > T && j == 1) continue;

            if (j > (i > T) + (i > S))
                chkmin(f[i][j], f[i - 1][j - 1] + Ll(i) + Lr(i));
            chkmin(f[i][j], f[i - 1][j + 1] + Gl(i) + Gr(i));
            if (i < S || j != 1)
                chkmin(f[i][j], f[i - 1][j] + Ll(i) + Gr(i));
            if (i < T || j != 1)
                chkmin(f[i][j], f[i - 1][j] + Gl(i) + Lr(i));
        }
    }
    if (T == n)
        f[n][1] = f[n - 1][1] + Gl(n);
    else if (S == n)
        f[n][1] = f[n - 1][1] + Gr(n);
    else
        f[n][1] = f[n - 1][2] + Gl(n) + Gr(n);

    cout << f[n][1] << '\n';
}