题解：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 longconst 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);elsef[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);elsef[n][1] = f[n - 1][2] + Gl(n) + Gr(n);cout << f[n][1] << '\n';
}