洛谷P2466 [SDOI2008] Sue 的小球题解

题目链接：P2466 [SDOI2008] Sue 的小球

题意：

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 各自的目标，你决定在收集到所有彩蛋的基础上，得到的分数最高。

对于 \(100\%\) 的数据，\(-10^4 \leq x_{i},y_{i},v_{i} \leq 10^4\)，\(N \leq 1000\)

首先先将彩蛋按 \(x\) 排序

因为可以左右走，可以想到这是一个区间dp

设 \(f_{0/1,i,j}\) 表示区间 \([i,j]\) 的彩蛋都被收集后的最小花费（代价），0/1表示此时在 \(i\) 还是 \(j\)

转移方程？

注意到当前的决策会受到之前决策的影响，也就是当前的时刻我们并不清楚

考虑增加一维？那就是暴力解法了

那怎么处理这个时刻的问题呢？

我们转化一下刚才的问题，

"当前的决策会受到之前决策的影响"

换句话说，就是当前的决策会影响之后的决策

也就是，现在的时刻会影响之后转移时的物品价值

考虑每次决策时，就把之后的代价先算进去

设 \(w_{i,j}\) 表示区间 \([i,j]\) 对之后决策造成的影响（代价），不难发现 \[ w_{i,j} = \sum_{i=0}^{n}v_i - \sum_{k=i}^{j}v_k \] 显然可以前缀和优化

当然最重要的是，我们可以~~很容易地~~推出转移方程了 \[ f_{0,i,j}=\min\left\{f_{0,i+1,j}+(x_{i+1}-x_i)\times(S_i+S_n-S_j),f_{1,i+1,j}+(x_j-x_i)\times(S_i+S_n-S_j)\right\} \\f_{1,i,j}=\min\left\{f_{0,i,j-1}+(x_j-x_i)\times(S_{i-1}+S_n-S_{j-1}), f_{1,i,j-1}+(x_j-x_{j-1})\times(S_{i-1}+S_n-S-{j-1})\right\} \] 其中 \(S_k = \sum_{i=1}^{k}v_k\)

时间复杂度 \(O(n^2)\)

答案就是 \(\sum y_i -\min\left\{f_{0,1,n},f_{1,1,n}\right\}\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e3+15)

int n,x0,f0[N][N],f1[N][N];
struct node{int x,y,v;}a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> x0;
    for(int i=1; i<=n; i++) cin >> a[i].x;
    for(int i=1; i<=n; i++) cin >> a[i].y;
    for(int i=1; i<=n; i++) cin >> a[i].v;
    a[++n].x=x0;
    sort(a+1,a+1+n,[](node a,node b){return a.x<b.x;});
    memset(f0,0x3f,sizeof(f0));memset(f1,0x3f,sizeof(f1));
    for(int i=1; i<=n; i++)
        if(a[i].x==x0){f0[i][i]=f1[i][i]=0;}
    for(int i=1; i<=n; i++) a[i].v+=a[i-1].v;
    for(int len=2; len<=n; len++)
        for(int i=1,j=i+len-1; j<=n; i++,j++)
        {
            f0[i][j]=min(f0[i+1][j]+(a[i+1].x-a[i].x)*(a[i].v+a[n].v-a[j].v),
                         f1[i+1][j]+(a[j].x-a[i].x)*(a[i].v+a[n].v-a[j].v));
            f1[i][j]=min(f0[i][j-1]+(a[j].x-a[i].x)*(a[i-1].v+a[n].v-a[j-1].v),
                         f1[i][j-1]+(a[j].x-a[j-1].x)*(a[i-1].v+a[n].v-a[j-1].v));
        }
    int sum=0;
    for(int i=1; i<=n; i++) sum+=a[i].y;
    cout << fixed << setprecision(3);
    cout << ((sum-min(f0[1][n],f1[1][n]))/1000.0) << '\n';
    return 0;
}