题解 P2466 【[SDOI2008]Sue的小球】

· · 题解

考虑先将彩蛋按 x 排序。现在我们从起点出发，此时 n 个彩蛋会以一定速度往下坠。射下一个彩蛋的分数是这个彩蛋被射下时的高度，自己的速度为 1，射击时间不计。问能够得到的最大分数。

首先，很显然的，因为射击不需要时间，所以说最优方案一定不会出现类似于 l \to r \to x(l < x< r) 的射击顺序。所以说在最优状态下，我们不会跳过没有被射下来的彩蛋去得到下一个彩蛋的分数，并且可以证明在最优状态的结束，我们一定停留在 1 或者 n。

于是考虑定义 dp_{l,r,0 \operatorname{or} 1} 为当前已得到了 [l,r] 彩蛋的分数，如果第三个数为 0，则我们停留在 l，否则停留在 r……呃，等等。我们是有时间的，如果将时间这一维加进去，时间不就显然爆炸了吗？

分析一下上面的状态，可以发现我们可以确定已经被收集掉了的彩蛋有哪些。而我们在拓展收集另外一个彩蛋的时候确确实实可以知道哪些彩蛋没有被收集。那么我们能不能将还没有收集的彩蛋下降的分数先加入我们的状态定义呢？

这样是可行的。因为我们能够发现彩蛋下降只会跟当前的时间有关系，所以可以将未来彩蛋下降的负贡献先加入到状态中，这样是没有问题的。

然后再想想怎么转移。对于一个区间 [l,r] 的状态，能够转移到这个区间的区间有 [l+1,r] 和 [l,r-1]。分类讨论取最大值即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Egg{
    LL x,y,v;
    Egg(){x=y=v=0;}
    Egg(LL X,LL Y,LL V){x=X,y=Y,v=V;}
    bool operator < (Egg ano) const {return x<ano.x;}
}egg[1005];
LL Abs(LL x){return x<0?-x:x;}
LL dp[1005][1005][2],sum[1005][1005],n,firx,totv;
int main(){
    memset(dp,128,sizeof dp);
    scanf("%lld %lld",&n,&firx);
    for(LL i=1;i<=n;++i)    scanf("%lld",&egg[i].x);
    for(LL i=1;i<=n;++i)    scanf("%lld",&egg[i].y);
    for(LL i=1;i<=n;++i)    scanf("%lld",&egg[i].v),totv+=egg[i].v;
    sort(egg+1,egg+1+n);
    for(LL i=1;i<=n;++i)    for(LL j=i;j<=n;++j)    sum[i][j]=sum[i][j-1]+egg[j].v;
    for(LL i=1;i<=n;++i)    dp[i][i][0]=dp[i][i][1]=egg[i].y-Abs(firx-egg[i].x)*totv;
    for(LL dis=2;dis<=n;++dis)
    {
        for(LL l=1,r=dis;r<=n;++l,++r)
        {
            dp[l][r][0]=max(dp[l+1][r][0]-(totv-sum[l+1][r])*(egg[l+1].x-egg[l].x),dp[l+1][r][1]-(totv-sum[l+1][r])*(egg[r].x-egg[l].x))+egg[l].y;
            dp[l][r][1]=max(dp[l][r-1][0]-(totv-sum[l][r-1])*(egg[r].x-egg[l].x),dp[l][r-1][1]-(totv-sum[l][r-1])*(egg[r].x-egg[r-1].x))+egg[r].y;
        }
    }
    printf("%.3f",double(max(dp[1][n][0],dp[1][n][1]))/1000.0);
    return 0;
}