P3089题解

· · 题解

题目传送门

思路

先将目标点按位置升序排序。

考虑朴素 dp（下文为正着跳的情况）。定义 dp_{i,j} 表示贝西当前在第 i 个点，且从第 j 个点跳跃过来能获得的最大得分。那么转移方程就为

dp_{i,j}=\max{dp_{j,k}+p_i}(k<j<i,x_j-x_k\le x_i-x_j)

显然，朴素的 dp 时间复杂度为 O(n^3)，不足以通过 n=1000 的数据。

考虑如何优化。注意到求 \max 的过程是 O(n) 的，所以可以想到用 st 表优化，这样求 \max 的复杂度就变成了 O(1) 的。

转移时，先二分出 k 的最小值，然后直接 O(1) 求出 \max。这样转移的复杂度就优化为 O(n^2\log n)。建表的复杂度也是 O(n^2\log n)，总的时间复杂度就是 O(n^2\log n)。空间复杂度 O(n^2\log n)，约为 40 MB，能通过本题。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,ans,lg[N],st[N][N][20];
struct drp
{
    int p,w;
}a[N];
bool cmp(drp x,drp y)
{
    return x.p<y.p;
}
int query(int id,int l,int r)
{
    int k=lg[r-l+1];
    return max(st[id][l][k],st[id][r-(1<<k)+1][k]);
}
int getp(int p,int dis)
{
    int l=1,r=p,pos=p;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if (a[p].p-a[mid].p>dis)
            l=mid+1;
        else
        {
            r=mid-1;
            pos=mid;
        }
    }
    return pos;
}
int getpf(int p,int dis)
{
    int l=p,r=n,pos=p;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if (a[mid].p-a[p].p>dis)
            r=mid-1;
        else
        {
            l=mid+1;
            pos=mid;
        }
    }
    return pos;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    lg[0]=-1;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].p>>a[i].w;
        lg[i]=lg[i>>1]+1;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        st[i][1][0]=a[1].w+(i>1?a[i].w:0);
        st[i][i][0]=a[i].w;
        for(int j=2;j<i;j++)
            st[i][j][0]=query(j,getp(j,a[i].p-a[j].p),j)+a[i].w;
        for(int k=1;k<=lg[i];k++)
            for(int j=1;j+(1<<k)-1<=i;j++)
                st[i][j][k]=max(st[i][j][k-1],st[i][j+(1<<(k-1))][k-1]);
        ans=max(ans,query(i,1,i));
    }
    memset(st,0,sizeof(st));
    for(int i=n;i>=1;i--)//还要反着跑一遍
    {
        st[i][n][0]=a[n].w+(i<n?a[i].w:0);
        st[i][i][0]=a[i].w;
        for(int j=i+1;j<n;j++)
        {
            st[i][j][0]=query(j,j,getpf(j,a[j].p-a[i].p))+a[i].w;
        }
        for(int k=1;k<=lg[n-i+1];k++)
            for(int j=i;j+(1<<k)-1<=n;j++)
                st[i][j][k]=max(st[i][j][k-1],st[i][j+(1<<(k-1))][k-1]);
        ans=max(ans,query(i,i,n));
    }
    cout<<ans<<"\n";
}