洛谷 P2466 [SDOI2008] Sue的小球 题解【动态规划】

点击量：781

题目看上去很麻烦，还是在坐标系里的，但是有区间特点“使用秘密武器得到一个彩蛋是瞬间的”。

目录

题目描述

Sue和Sandy最近迷上了一个电脑游戏，这个游戏的故事发在美丽神秘并且充满刺激的大海上，Sue有一支轻便小巧的小船。然而，Sue的目标并不是当一个海盗，而是要收集空中漂浮的彩蛋，Sue有一个秘密武器，只要她将小船划到一个彩蛋的正下方，然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而，彩蛋有一个魅力值，这个魅力值会随着彩蛋在空中降落的时间而降低，Sue要想得到更多的分数，必须尽量在魅力值高的时候收集这个彩蛋，而如果一个彩蛋掉入海中，它的魅力值将会变成一个负数，但这并不影响Sue的兴趣，因为每一个彩蛋都是不同的，Sue希望收集到所有的彩蛋。

 

然而Sandy就没有Sue那么浪漫了，Sandy希望得到尽可能多的分数，为了解决这个问题，他先将这个游戏抽象成了如下模型：

 

以Sue的初始位置所在水平面作为x轴。

 

一开始空中有N个彩蛋，对于第i个彩蛋，他的初始位置用整数坐标（xi, yi）表示，游戏开始后，它匀速沿y轴负方向下落,速度为vi单位距离/单位时间。Sue的初始位置为(x0, 0)，Sue可以沿x轴的正方向或负方向移动，Sue的移动速度是1单位距离/单位时间，使用秘密武器得到一个彩蛋是瞬间的，得分为当前彩蛋的y坐标的千分之一。

 

现在，Sue和Sandy请你来帮忙，为了满足Sue和Sandy各自的目标，你决定在收集到所有彩蛋的基础上，得到的分数最高。

输入输出格式

输入格式：

第一行为两个整数N, x0用一个空格分隔，表示彩蛋个数与Sue的初始位置。

 

第二行为N个整数xi，每两个数用一个空格分隔，第i个数表示第i个彩蛋的初始横坐标。

 

第三行为N个整数yi，每两个数用一个空格分隔，第i个数表示第i个彩蛋的初始纵坐标。

 

第四行为N个整数vi，每两个数用一个空格分隔，第i个数表示第i个彩蛋匀速沿y轴负方向下落的的速度。

 

输出格式：

一个实数，保留三位小数，为收集所有彩蛋的基础上，可以得到最高的分数。

 

输入输出样例

输入样例#1：

3 0

-4 -2 2

22 30 26

1 9 8

输出样例#1：

0.000

说明

对于30%的数据，N<=20。

 

对于60%的数据，N<=100。

 

对于100%的数据，-10^4 <= xi,yi,vi <= 10^4，N < = 1000

 

  这个题目曾被引用到集训队论文中，是一道典型的费用提前计算问题，因为对时间做DP的话，极限情况会达到$ 10000 \times 1000$空间上就会超限，因此我们不能利用时间，而把时间用另一种形式存起来，也就是费用提前计算，可见P1220关路灯是类似这个题的“不用费用提前”版本。

  同时，这个题需要离散化，不然负数和较大间隔当然影响我们遍历，为了方便，我们把这个点加入，使得点总数为n+1。

  有了这个，我们的dp数组就出来了，f[k][i][j]表示打完i到j（保证i<j）后最小花费，k=1时表示打完后人在i点（左侧），k=2时表示打完后人在j点。

  根据贪心，打掉头顶上的彩蛋不需要消耗时间，因此从x0向左右扩展时，如果向左扩展，一定是打掉左边最靠近自己的彩蛋，这样状态才能转移。所以上面的f数组中人一定是站在i点或j点的。

  如何计算状态转移过程中的花费呢？我们想，在人走动过程中，彩蛋也在随之下落，那么每下落1个单位，得分会减少1，因此在这过程中没有捡到的彩蛋下落的距离就是我们损失的花费。

  f[1][i][j]表示人目前站在i点的已经打完i~j的状态。如果它要转移至f[1][i-1][j]，那么当前处于1到i-1，和j+1到n+1的彩蛋都下落了i到i-1的水平距离的时间，并且还要乘它们的速度。速度这里可以用前缀和存一下，也就是可以直接调用1到i-1的速度了。记住被打掉的点不能忘记。

  因为上文中提到我们有n+1个点，所以做完后，找到花费最小的是

min(f[1][1][n+1],f[2][1][n+1]);

  然而题目让我们输出得分，那么分析一下，如果没有花费，即每个彩蛋的速度都为0，就是理想得分，用理想得分减去花费就是实际得分了。注意因为所有得分都是千分之一，所以只需要对结果除上1000即可（记得用double输出并加上eps（精度参数），不然小数点后会是0）。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
using std::min;
int f[3][1002][1002];//f[1][i][j]表示人站在i
int b[1002];
struct node
{
    int x,y,v;
    friend bool operator <(node a,node b)//方便离散化
    {
        return a.x<b.x;
    }
}pnt[1008];
int main()
{
    memset(f,0x3f,sizeof(f));
    int n,x0;
    scanf("%d%d",&n,&x0);
    for(int i=1;i<=n;i++)
        scanf("%d",&pnt[i].x);
    for(int i=1;i<=n;i++)
        scanf("%d",&pnt[i].y);
    for(int i=1;i<=n;i++)
        scanf("%d",&pnt[i].v);
    pnt[n+1].x=x0;
    pnt[n+1].y=0;
    pnt[n+1].v=0;
    int tmp;
    std::sort(pnt+1,pnt+n+2);
    for(int i=1;i<=n+1;i++)
        b[i]=b[i-1]+pnt[i].v;
    for(int i=1;i<=n+1;i++)
        if(pnt[i].x==x0&&pnt[i].v==0)
        {
            tmp=i;
            break;
        }
    f[1][tmp][tmp]=0;
    f[2][tmp][tmp]=0;
    for(int l=1;l<=n;l++)
        for(int i=max(tmp-l,1);i<=min(tmp,n+1-l);i++)//保证了包含tmp
        {
            f[1][i][i+l]=min(f[1][i+1][i+l]+(pnt[i+1].x-pnt[i].x)*(b[i] +b[n+1]-b[i+l]),
            //从i+1或i+l过来                          ^距离         ^其他（包括即将打掉的）彩蛋下落高度和
                            f[2][i+1][i+l]+(pnt[i+l].x-pnt[i].x)*(b[i] +b[n+1]-b[i+l]));
            f[2][i][i+l]=min(f[1][i][i+l-1]+(pnt[i+l].x-pnt[i].x)*(b[i-1] +b[n+1]-b[i+l-1]),
                            f[2][i][i+l-1]+(pnt[i+l].x-pnt[i+l-1].x)*(b[i-1] +b[n+1]-b[i+l-1]));
            //从i或i+l-1过来
        }
    int sum=0;
    for(int i=1;i<=n+1;i++)
        sum+=pnt[i].y;
    printf("%.3lf\n",(sum-min(f[1][1][n+1],f[2][1][n+1])+0.0)/1000);
    return 0;
}