题目：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3315

DP,f[i][j]表示当前在i，上一步在j的最大值，f[i][j]=max(f[j][k])+p[i],刚开始我想要用BIT维护，后来ORZ了题解之后发现傻了，由于DP过程中(从左往右)，k明显是递减的，那么直接动态维护[k..j]就可以了。复杂度：O( n^2 )

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
#define MAXN 1010
 
struct node{
        int x,p;
} a[MAXN];
 
bool cmp(node x,node y){
        return x.x<y.x;
}
 
bool Cmp(node x,node y){
        return x.x>y.x;
}
 
int f[MAXN][MAXN],n,ans=0;
int Max[MAXN][2];
 
int main(){
        scanf("%d",&n);
        for(int i=0;i++<n;){
               scanf("%d%d",&a[i].x,&a[i].p);
        }
        sort(a+1,a+n+1,cmp);
        memset(f,0,sizeof(f));
        memset(Max,0,sizeof(Max));
        for(int i=0;i++<n;){
               f[i][i]=Max[i][1]=a[i].p;
               Max[i][0]=i;
        }
        for(int i=0;i++<n;){
               for(int j=0;j++<i-1;){
                       while(a[j].x-a[Max[j][0]-1].x<=a[i].x-a[j].x&&(Max[j][0]-1)){
                               Max[j][0]--;
                               Max[j][1]=max(Max[j][1],f[j][Max[j][0]]);
                       }
                       f[i][j]=max(f[i][j],Max[j][1]+a[i].p);
               }
        }
        for(int i=0;i++<n;)for(int j=0;j++<n;) ans=max(ans,f[i][j]);
        memset(f,0,sizeof(f));
        memset(Max,0,sizeof(Max));
        for(int i=n;i;i--){
               Max[i][1]=f[i][i]=a[i].p;
               Max[i][0]=i;
               for(int j=i;j++<n;){
                       while(a[Max[j][0]+1].x-a[j].x<=a[j].x-a[i].x&&Max[j][0]<n){
                               Max[j][1]=max(Max[j][1],f[j][++Max[j][0]]);
                       }
                       f[i][j]=max(f[i][j],Max[j][1]+a[i].p);
               }
        }
        for(int i=0;i++<n;)for(int j=0;j++<n;) ans=max(ans,f[i][j]);
        printf("%d\n",ans);
        return 0;
}