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

作者: wjyyy 分类: DP,模拟,解题报告,贪心 发布时间: 2018-05-22 15:50

点击量:41

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

题目描述

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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */