题目
Sue 和 Sandy 最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上，Sue 有一支轻便小巧的小船。然而，Sue 的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋，Sue 有一个秘密武器，只要她将小船划到一个彩蛋的正下方，然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而，彩蛋有一个魅力值，这个魅力值会随着彩蛋在空中降落的时间而降低，Sue 要想得到更多的分数，必须尽量在魅力值高的时候收集这个彩蛋，而如果一个彩蛋掉入海中，它的魅力值将会变成一个负数，但这并不影响 Sue 的兴趣，因为每一个彩蛋都是不同的，Sue 希望收集到所有的彩蛋。
然而 Sandy 就没有 Sue 那么浪漫了，Sandy 希望得到尽可能多的分数，为了解决这个问题，他先将这个游戏抽象成了如下模型：
将大海近似的看做 \(x\) 轴，以 Sue 所在的初始位置作为坐标原点建立一个竖直的平面直角坐标系。
一开始空中有 \(N\) 个彩蛋，对于第 \(i\) 个彩蛋，他的初始位置用整数坐标 \((x_{i}, y_{i})\) 表示，游戏开始后，它匀速沿 \(y\) 轴负方向下落,速度为 \(v_{i}\) 单位距离/单位时间。Sue 的初始位置为 \((x_{0}, 0)\)，Sue 可以沿 \(x\) 轴的正方向或负方向移动，Sue 的移动速度是 \(1\) 单位距离/单位时间，使用秘密武器得到一个彩蛋是瞬间的，得分为当前彩蛋的 \(y\) 坐标的千分之一。
现在，Sue 和 Sandy 请你来帮忙，为了满足 Sue 和 Sandy 各自的目标，你决定在收集到所有彩蛋的基础上，得到的分数最高。
分析
一开始一直在想普通的 dp 究竟要怎么设状态，可是无论怎么设都无法在避免前面的彩蛋对后面所有彩蛋造成的影响，如果要避免的话复杂度里总是会有个坐标轴值域大小，显然会 T，而且初始位置在彩蛋的中间更不好按照彩蛋的顺序转移了，于是只好看题解。
第一篇题解引用了论文「对一类动态规划问题的研究」By 湖南省长沙市第一中学 徐源盛 ，主旨是如果当前的决策对未来的行动会造成影响，那么决策的时候就把影响计算出来就是了。
不过在这之前，我们需要先注意到一点：从起点到当前位置的路径上的彩蛋是必然会拿的，这是很显然的，但是为什么我当时没有注意到啊 kora！，也就是说每次拿取到的彩蛋必然是一段区间，所以当然要用区间 DP 而不是普通的 DP 啦！
然后我们将论文中的思想运用到这道题中，其实思想也很 intuitive，感觉主要困扰我的是没有想到用区间 DP（哭）。在这道题中，我们设 \(f[i][j]\) 表示已经取得了区间 i 到 j 的彩蛋的得分，但是很快发现下一步拓展到 \(i-1\) 和 \(j+1\) 的计算结果会和当前的位置是在 \(i\) 还是 \(j\) 有关，这个简单，加一维分别表示最后是在左边还是右边就好了，于是有了 \(f[0][i][j]\) 和 \(f[1][i][j]\) 分别表示在 \(i\) 和在 \(j\)。
这样一来，状态转移方程就很简单了，如果是求 \(f[0][i][j]\)，分别考虑是从 \(f[0][i+1][j]\) 还是 \(f[1][i+1][j]\) 拓展来的就好了。
假设彩蛋的收益是 \(y\)，位置为 \(x\)，我们已经取得了的彩蛋区间为 \([i,j]\)，去取彩蛋 \(i\) 所需要的时间为 \(t\)，那么对所有未取得的彩蛋的影响为 \(cost=(\sum_{k=1}^nv_k-\sum_{k=i+1}^jv_k)t\)，于是有状态转移方程：
\[f[0][i][j]=y_i+\max(f[0][i+1][j]-cost*(x_{i+1}-x_i)),f[1][i+1][j]-cost*(x_j-x_i)) \]第一维取值为 1 的状态转移方程也是类似的。
最后要吐槽的是我居然忘了区间 DP 枚举的第一维是区间长度而不是区间左边的值，如果按照区间 \([i,j]\) 这样来枚举 \(i\) 和 \(j\) 会导致两个都需要求的 \(f\) 互相调用对方的值来求得自己的值，这样就假了，因为每次转移是从区间长度小 1 的状态转移来的，把区间长度作为第 1 维进行枚举的话就可以保证每次转移依赖的值都是已经求解过的真值。
代码
#include <bits/stdc++.h>
using std::cin; using std::cout;
using std::max; using i64 = long long;
const int N = 1005;
struct egg {
i64 x, y, v;
} e[N];
int n;
i64 m;
i64 f[2][N][N], s[N];
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> e[i].x;
for (int i = 1; i <= n; ++i) cin >> e[i].y;
for (int i = 1; i <= n; ++i) cin >> e[i].v;
e[++n] = (egg){ m, 0, 0 };
std::sort(e + 1, e + 1 + n, [](egg T1, egg T2) { return T1.x < T2.x; });
int pos = 0;
for (int i = 1; i <= n; ++i) {
if (e[i].x == m) pos = i;
s[i] = s[i - 1] + e[i].v;
}
memset(f, -0x3f3f3f3f, sizeof(f));
f[0][pos][pos] = f[1][pos][pos] = 0;
auto cost = [](int i, int j) { return s[n] - (s[j] - s[i - 1]); };
for (int k = 1; k <= n; ++k) {
for (int i = 1, j; i + k <= n; ++i) {
j = i + k;
f[0][i][j] = e[i].y + max(f[0][i + 1][j] - (e[i + 1].x - e[i].x) * cost(i + 1, j),
f[1][i + 1][j] - (e[j].x - e[i].x) * cost(i + 1, j));
f[1][i][j] = e[j].y + max(f[0][i][j - 1] - (e[j].x - e[i].x) * cost(i, j - 1),
f[1][i][j - 1] - (e[j].x - e[j - 1].x) * cost(i, j - 1));
}
}
printf("%.3lf", 1.0 * max(f[0][1][n], f[1][1][n]) / 1000);
return 0;
}