LuoguP3089 [USACO13NOV]POGO的牛Pogo-Cow

· · 题解

题目链接戳这里

简明题意

--- 首先第一步当然是把这些点按照坐标从小到大排序啦。 # ~~会MLE~~的DP做法 定义 $f(i,j)$ 表示当前 $Betty$ 跳到了第 $i$ 个点，且最小跳跃距离为 $j$ 的最大总得分。很容易得到状态转移方程： $$f(i,j)=\max\{f(j,k)+s(i)\}(0\leq k\leq j)$$ 显然又会 `MLE` 又会 `TLE`。 # 正常 DP 做法 由于 $Betty$ **只朝一个方向跳跃**，所以要分两种情况：一种是一直向右跳，一种是一直向左跳。 当一直向右跳时，定义 $f(i,j)$ 表示当前 $Betty$ 已经跳到了第 $i$ 个点，且最后一步是从第 $j$ 个点跳到第 $i$ 个点的最大总得分。那么 $$f(i,j)=\max\{f(j,k)+s(i)\}$$ 其中 $k<j<i$，$x(j)-x(k)\leq x(i)-x(j)$。 考虑边界 $f(i,i)=s(i)$。（即一开始站在任意一个点上） 当一直向左跳时也同理，只不过方向倒过来而已。只要做两次 `DP` 就可以了。 这个时候时间复杂度为 $O(N^3)$，由于数据水，期望 $81pts$。 # 优化 第一步显然：$f(i,j)=\max\{f(j,k)+s(i)\}=\max\{f(j,k)\}+s(i)

第二步：我们观察式子：

f(i-1,j)=\max\{f(j,k)\}+s(i-1)

我们发现和原来的式子非常像，好像可以直接 f(i,j)=f(i-1,j)-s(i-1)+s(i)，但是上面的式子定义范围会变成了x(j)-x(k)\leq x(i-1)-x(j)。由于 x(i-1)<x(i)，所以满足条件的 k 会变多！所以我们需要将拓展到的 k 先取一个最大值，然后才能直接转移。

因为这个时候我们是从 i-1 转移到 i 的，所以我们要先枚举 j，再枚举 i。

for(int j=1;j<=N;j++){
    f[j][j]=s(j);//边界
    for(int i=j+1,now=j+1;i<=N;i++){
        f[i][j]=f[i-1][j]-s(i-1);//先得到之前的max
        while(now>1 && x(j)-x(now-1)<=x(i)-x(j))
            f[i][j]=max(f[i][j],f[j][--now]);//取拓展到k的最大值
        f[i][j]+=s(i);//直接转移
        Ans=max(Ans,f[i][j]);
    }
}

如果是一直往左跳，就反着做一遍 DP 就可以了。

由于每个k 只会被拓展 1 次，时间复杂度为 O(N^2)。

程序

#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
    char ch=getchar();int f=1,num=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){num=num*10+ch-'0';ch=getchar();}
    return num*f;
}
int N,f[1002][1002],Ans;
struct Point{int x,s;} point[1002];
bool cmp(Point a,Point b){return a.x<b.x;}
#define x(i) point[i].x
#define s(i) point[i].s
int main(){
    N=read();
    for(int i=1;i<=N;i++)x(i)=read(),s(i)=read();
    sort(point+1,point+1+N,cmp);
    for(int j=1;j<=N;j++){
        f[j][j]=s(j);//边界
        for(int i=j+1,now=j+1;i<=N;i++){
            f[i][j]=f[i-1][j]-s(i-1);//先得到之前的max
            while(now>1 && x(j)-x(now-1)<=x(i)-x(j))
                f[i][j]=max(f[i][j],f[j][--now]);//取拓展到k的最大值
            f[i][j]+=s(i);//直接转移
            Ans=max(Ans,f[i][j]);
        }
    }
    for(int j=N;j>=1;j--){
        f[j][j]=s(j);
        for(int i=j-1,now=j-1;i>=1;i--){
            f[i][j]=f[i+1][j]-s(i+1);
            while(now<N && x(now+1)-x(j)<=x(j)-x(i))
                f[i][j]=max(f[i][j],f[j][++now]);
            f[i][j]+=s(i);
            Ans=max(Ans,f[i][j]);
        }
    }
    printf("%d",Ans);
    return 0;
}