给定 n n n头牛以一维坐标轴的位置 x x x和贡献 p p p,一个人可以任选一个牛的位置作为出发点,只能往一个方向跳的下一头牛的位置,求可以获得最大贡献。
显然需要先对牛按位置排序,然后分两种情况,往左和往右,因为这两种情况解决的方法是一样的,我们只需先考虑一种,比如往右。因为 n = 1 0 3 n=10^3 n=103,在提示我们是 n 2 n^2 n2的思路,考虑区间 d p dp dp,令 d p [ j ] [ i ] dp[j][i] dp[j][i]表示从第 j j j头牛走到第 i i i头牛的最大贡献。有转移方程: d p [ j ] [ i ] = m a x ( d p [ j ] [ i ] , d p [ k ] [ j ] + a [ i ] . p ) dp[j][i]=max(dp[j][i],dp[k][j]+a[i].p) dp[j][i]=max(dp[j][i],dp[k][j]+a[i].p),类似于合并区间。
这个复杂度最大是 O ( n 3 ) O(n^3) O(n3),但是因为有条件限制 d i s ( k , j ) ≤ d i s ( j , i ) dis(k,j)\le dis(j,i) dis(k,j)≤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 ) O(1) O(1)的,同时维护一个 m x [ i ] [ j ] mx[i][j] mx[i][j]表示区间 [ i , j ] [i,j] [i,j]内以 j j j终点的最大值。