洛谷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\le x_i,y_i,v_i\le 10^4$，$N\le 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$$
显然可以前缀和优化

当然最重要的是，我们可以很容易地推出转移方程了
$$\begin{gathered} 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\} \end{gathered}$$
其中 $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;
}

参考文献

[1] https://www.luogu.com.cn/blog/Bartholomew/solution-p2466

转载请说明出处