Pogo-Cow(区间dp)

题意

​ 给定$n$头牛以一维坐标轴的位置$x$和贡献$p$，一个人可以任选一个牛的位置作为出发点，只能往一个方向跳的下一头牛的位置，求可以获得最大贡献。

思路

​ 显然需要先对牛按位置排序，然后分两种情况，往左和往右，因为这两种情况解决的方法是一样的，我们只需先考虑一种，比如往右。因为$n=10^3$，在提示我们是$n^2$的思路，考虑区间$dp$，令$dp[j][i]$表示从第$j$头牛走到第$i$头牛的最大贡献。有转移方程：$dp[j][i]=max(dp[j][i],dp[k][j]+a[i].p)$，类似于合并区间。

这个复杂度最大是$O(n^3)$，但是因为有条件限制$dis(k,j)\le dis(j,i)$，是可以过掉的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int dp[N][N];//从i走到j的最大值
struct node{
    int x,p;
}a[N];
bool cmp(node a,node b){
    return a.x<b.x;
}
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].p;
    sort(a+1,a+n+1,cmp);
    int ans=0;
    for(int i=1;i<=n;i++){
        dp[i][i]=a[i].p;
        for(int j=i-1;j;j--){// j to i
             int d2=a[i].x-a[j].x;
            for(int k=j;k;k--){ // k to j
                int d1=a[j].x-a[k].x;
                if(d1>d2) break;
                dp[j][i]=max(dp[j][i],dp[k][j]+a[i].p);
            }
            ans=max(ans,dp[j][i]);
        }
    }
    mst(dp,0);
    for(int i=n;i;i--){
        dp[i][i]=a[i].p;
        for(int j=i+1;j<=n;j++){// j to i
             int d2=a[j].x-a[i].x;
            for(int k=j;k<=n;k++){ // k to j
                int d1=a[k].x-a[j].x;
                if(d1>d2) break;
                dp[i][j]=max(dp[i][j],dp[j][k]+a[i].p);
            }
            ans=max(ans,dp[i][j]);
        }
    }
        printf("%d\n",ans);
	return 0;
}

另外，第三维应该是可以做到$O(1)$的，同时维护一个$mx[i][j]$表示区间$[i,j]$内以$j$终点的最大值。