蒟蒻的小窝

蒟蒻的小窝

题解 P3089 【[USACO13NOV]Pogo-Cow S】

posted on 2020-08-15 20:16:08 | under 题解 |

拿到这道题就会有一个 $n^3$ 的方法, $f[j][i]$ 表示第j个人跳到 $i$,之后枚举一个 $k$, $f[j][i]=max(f[j][i],f[i][k]+a[j].v);$ (但为了好写代码里写的是 $f[i][j]$ ,这里写 $f[j][i]$ 方便解释)这是 $n^3$ 的方法(实测不开 $O2$ 能过),那有没有更优秀的方法呢?我们发现,当 $i$ 往后推了一位的时候,也就是 $f[j][i+1]$,原本 $f[j][i]$ 所能用到的 $j$ 都能用到,也就是下次再推 $j$ 的时候只需要从 $f[j][i]$ 的 $j$ 往前继续推就可以了,这里用单调队列来实现,就把时效降到了 $n^2$。但是!!!千万要注意,“只允许朝一个方向跳跃”,是指贝西要么只能往左跳,要么只能往右跳,所以要刷两趟 $dp$ ,向右跳的直接就处理掉了,而往左跳怎么处理呢?把每个坐标都 $*-1$,然后再把整个序列翻转就 $ok$ 了,为什么要乘 $-1$ 呢,是因为要把它们的间距改掉嘛。

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1005;
struct ha{
    int x,p;
    bool operator<(const ha&b)const{return x<b.x;}
}a[maxn];
int n,f[maxn][maxn],ans;
inline int red(){
    int tot=0;char ch=getchar();
    while (ch<'0'||'9'<ch) ch=getchar();
    while ('0'<=ch&&ch<='9') tot=tot*10+ch-48,ch=getchar();
    return tot;
}
void DP(){
    memset(f,192,sizeof(f));
    for (int i=1;i<=n;i++) f[i][i]=a[i].p;
    for (int j=1;j<n;j++){
        int k=j,Max=f[j][j];
        for (int i=j+1;i<=n;i++){
            while (k&&a[j].x-a[k].x<=a[i].x-a[j].x) Max=max(Max,f[k--][j]);
            f[j][i]=Max+a[i].p;
            ans=max(ans,f[j][i]);
        }
    }
}
int main(){
    n=red();
    for (int i=1;i<=n;i++) a[i].x=red(),a[i].p=red();
    sort(a+1,a+1+n);
    DP();
    for (int i=1;i<=n;i++) a[i].x*=-1;
    reverse(a+1,a+1+n);
    DP();
    printf("%d\n",ans);
    return 0;
}