[SDOI2008] Sue 的小球 题解

题目描述

首先将彩蛋按照横坐标从小到大排序，依次标号为 \(1\sim n\)。

显然，\(Sue\)走过一段时间后，走过的点一定属于一段连续区间。所以本题采用区间 \(dp\)。

不妨先做一个简单转化，由于每个彩蛋初始高度确定，若想让总分最高，就要使扣分最少。所以下面的 \(dp\) 从扣分最少入手。

设 \(f_{l,r,0/1}\) 表示走过 \(l\sim r\) 所有点，现在处于 \(l/r\)，扣的最少分。

转移的关键就是处理时间。

其中一种显然的想法是，如果能处理当前的时间，那么由 \(A\)（当前点） 点走到 \(B\) 点，就能计算出到达 \(B\) 点的时间，并相应扣除分值，但是这样不得不在状态中加多一维时间，即 \(f_{l,r,t,0/1}\)，空间爆炸，不行。

刚刚的想法将所有点独立，即到达一个点在计算贡献，不妨将所有点看做整体。具体而言，从 \(A\) 点到 \(B\) 点需要时间 \(t\)，计算没经过的点在时间 \(t\) 内损失的分值。设没经过的点速度总值为 \(sv\)，那么损失分支为 \(sv\times t\)。

由于这种方法中，两点之间时间可计算，经过哪些点从状态 \(l,r\) 可知，速度总值前缀和计算即可。

剩下转移看代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=1100;
int n,st;
LL f[N][N][2],sv[N];
struct node {
    int x,y,v;
}a[N];

int cmp(node x,node y) {
    return x.x<y.x;
}

LL calc(int l,int r) {
    return sv[r]-sv[l-1];
}

int main(){
    cin>>n>>st;
    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;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++) {
        sv[i]=sv[i-1]+a[i].v;
    }
    LL vsum=sv[n];
    memset(f,0x3f,sizeof(f));
    //损失的最小值
    for(int i=1;i<=n;i++) {
        f[i][i][0]=f[i][i][1]=1ll*abs(st-a[i].x)*vsum;
    }

    // for(int i=1;i<=n;i++) cout<<f[i][i][0]<<" ";

    for(int len=2;len<=n;len++) {
        for(int l=1;l+len-1<=n;l++) {
            int r=l+len-1;
            f[l][r][0]=min({f[l][r][0],f[l+1][r][0]+1ll*(a[l+1].x-a[l].x)*(vsum-calc(l+1,r)),f[l+1][r][1]+1ll*(a[r].x-a[l].x)*(vsum-calc(l+1,r))});
            f[l][r][1]=min({f[l][r][1],f[l][r-1][1]+1ll*(a[r].x-a[r-1].x)*(vsum-calc(l,r-1)),f[l][r-1][0]+1ll*(a[r].x-a[l].x)*(vsum-calc(l,r-1))});
            f[l][r][0]=min(f[l][r][0],f[l][r][1]+1ll*(a[r].x-a[l].x)*(vsum-calc(l,r)));
            f[l][r][1]=min(f[l][r][1],f[l][r][0]+1ll*(a[r].x-a[l].x)*(vsum-calc(l,r)));

            // cout<<"DEBUG:"<<"["<<l<<" "<<r<<"]:"<<f[l][r][0]<<" "<<f[l][r][1]<<endl;
        }
    }
    LL ysum=0;
    for(int i=1;i<=n;i++) ysum+=a[i].y;
    LL ans=ysum-min(f[1][n][0],f[1][n][1]);
    printf("%.3lf",ans/1000.0);
    return 0;
}
/*
*/