DP【洛谷P3089】 [USACO13NOV]POGO的牛Pogo-Cow

【洛谷P3089】 [USACO13NOV]POGO的牛Pogo-Cow

设\(f(i)(j)\)表示第i个点从j转移过来的最优解，朴素\(n^3\)。

正反来两边，特判k=0；

正解单调队列优化，可是我不会。

洛谷上\(n^3\)水过。

我菜我菜。

code：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define int long long

using namespace std;

const int wx=2017;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

struct node{

	int x,p;

	friend bool operator < (const node & a,const node & b){

		return a.x<b.x;

	}

}t[wx];

int f[wx][wx];

int n,ans;

signed main(){

	n=read();

	for(int i=1;i<=n;i++)t[i].x=read(),t[i].p=read();

	sort(t+1,t+1+n);

	for(int i=1;i<=n;i++)f[i][0]=t[i].p;

	for(int i=1;i<=n;i++){

		for(int j=1;j<i;j++){

			for(int k=0;k<j;k++){

				if(k&&t[j].x-t[k].x<=t[i].x-t[j].x)f[i][j]=max(f[i][j],f[j][k]+t[i].p);

				else if(!k)f[i][j]=max(f[i][j],f[j][k]+t[i].p);

			}

			ans=max(ans,f[i][j]);

		}

	}

	memset(f,0,sizeof f);

	for(int i=1;i<=n;i++)t[i].x=t[n].x-t[i].x+1;

	sort(t+1,t+1+n);

	for(int i=1;i<=n;i++)f[i][0]=t[i].p;

	for(int i=1;i<=n;i++){

		for(int j=1;j<i;j++){

			for(int k=0;k<j;k++){

				if(k&&t[j].x-t[k].x<=t[i].x-t[j].x)f[i][j]=max(f[i][j],f[j][k]+t[i].p);

				else if(!k)f[i][j]=max(f[i][j],f[j][k]+t[i].p);

			}

			ans=max(ans,f[i][j]);

		}

	}

	printf("%lld\n",ans);

	return 0;

}

/*

6

5 6

1 1

10 5

7 6

4 8

8 10

*/