洛谷2466 [SDOI2008]Sue的小球

题意

有 $N$ 个小球，每个小球的坐标为 $(x_i,y_i)$ ，即水平为 $x_i$ ，高度为 $y_i$ ， 每秒会以 $v_i$ 的速度下落。人所在的初始位置为 $x_0$ ，每秒可以移动一个单位。

当人移动到小球下面的时候就可以接住这个小球并获得分数，分数为小球当前高度的 $\dfrac{1}{1000}$ 。要求接住所有小球，求最高分数。

$N\le 1000$ 。

题解

比较容易想到区间DP，用 $f[l][r][0]$ 表示接住了 $[l,r]$ 的小球，现在在 $l$ 的最高分；$f[l][r][1]$ 表示现在在 $r$ 。

但是这个状态并不能表示时间，所以就不能直接算出代价。

不过可以把小球因下落而损失的分数记录在状态里。如果上次涂 $l+1$ ，那么 $[r+1,n]$ 和 $[1,l]$ 每秒都会损失 $v_i$ 的分数，对 $v$ 做一次前缀和 $w_i$ 就可以算出。方程式为：

$$f[l][r][0]=\max_{k=l}^{r-1}(f[l+1][r][0]-(x_{l+1}-x_l)\times (w_n-w_r+w_l),f[l+1][r][1]-(x_r-x_l)\times (w_n-w_r+w_l),) \\ f[l][r][1]=\max_{k=l}^{r-1}(f[l][r-1][0]-(x_r-x_l)\times (w_n-w_{r-1}+w_{l-1}),f[l][r-1][1]-(x_r-x_{r-1})\times (w_n-w_{r-1}+w_{l-1}))$$

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct node {
    int x,y,v;
} s[1005];
const int inf=-1044266559;
int n,x0,w[1005],f[1005][1005][2];

int dfs(int l,int r,bool x)
{
    int &ans=f[l][r][x];
    if (ans!=inf) return ans;
    if (l==r) return inf;
    if (!x) ans=s[l].y+max(dfs(l+1,r,0)-(s[l+1].x-s[l].x)*(w[n]-w[r]+w[l]),
                           dfs(l+1,r,1)-(s[r].x-s[l].x)*(w[n]-w[r]+w[l]));
    else ans=s[r].y+max(dfs(l,r-1,0)-(s[r].x-s[l].x)*(w[n]-w[r-1]+w[l-1]),
                        dfs(l,r-1,1)-(s[r].x-s[r-1].x)*(w[n]-w[r-1]+w[l-1]));
    return ans;
}

signed main()
{
    n=read(); x0=read();
    for (int i=1;i<=n;i++) s[i].x=read();
    for (int i=1;i<=n;i++) s[i].y=read();
    for (int i=1;i<=n;i++) s[i].v=read();
    s[++n]=(node){x0,0,0};
    sort(s+1,s+n+1,[](const node &x,const node &y){ return x.x<y.x; });
    memset(f,-0x3f,sizeof(f));
    for (int i=1;i<=n;i++)
    {
        w[i]=w[i-1]+s[i].v;
        if (s[i].x==x0 && !s[i].y) f[i][i][0]=f[i][i][1]=0;
    }
    return !printf("%.3f",1.0*max(dfs(1,n,0),dfs(1,n,1))/1000);
}