原题链接

题解

暴力dp：
遍历 \(i,j,k\) ，\(dp[i][j]=\max(dp[j][k])+v_i\) 其中 \(x_i-x_j\geq x_j-x_k\)

优化：
对于 \(j\) 来说 ，随着 \(i\) 越大， \(k\) 可以越小，因此省去了遍历一层 \(k\) ，而是维护每个点的 \(k\) ，（反正求的是最大值）

细节

1.有两个方向
2.任意起点

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;

struct node
{
    int x,v;
}star[1005];

int mx[1005]={0},last[1005];
int dp[1005][1005]={0};

bool cmp1(node a,node b)
{
    return a.x<b.x;
}
bool cmp2(node a,node b)
{
    return a.x>b.x;
}


void solve()
{
    int n;
    cin>>n;

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>star[i].x>>star[i].v;
        ans=max(ans,star[i].v);
    }

    sort(star+1,star+1+n,cmp1);
    for(int i=1;i<=n;i++)
    {
        last[i]=i-1;
        mx[i]=star[i].v;
        for(int j=1;j<i;j++)
        {
            while(last[j]>0&&star[i].x-star[j].x>=star[j].x-star[last[j]].x)
            {
                mx[j]=max(mx[j],dp[j][last[j]]);
                last[j]--;
            }
            dp[i][j]=mx[j]+star[i].v;
            ans=max(ans,dp[i][j]);
            //printf("i:%d   j:%d  dp:%d\n",i,j,dp[i][j]);
        }
        dp[i][i]=star[i].v;
       // printf("i:%d   j:%d  dp:%d\n",i,i,dp[i][i]);
    }


    sort(star+1,star+1+n,cmp2);

    for(int i=1;i<=n;i++)
    {
        last[i]=i-1;
        mx[i]=star[i].v;
        for(int j=1;j<i;j++)
        {
            while(last[j]>0&&star[j].x-star[i].x>=star[last[j]].x-star[j].x)
            {
                mx[j]=max(mx[j],dp[j][last[j]]);
                last[j]--;
            }
            dp[i][j]=mx[j]+star[i].v;
            ans=max(ans,dp[i][j]);
          //  printf("i:%d   j:%d  dp:%d\n",i,j,dp[i][j]);
        }
        dp[i][i]=star[i].v;
       // printf("i:%d   j:%d  dp:%d\n",i,i,dp[i][i]);
    }

    cout<<ans;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}