noip快要来了 要练练dp 难度也挺接近 还是挺好的
| [Usaco2013 Nov]Pogo-Cow |
这一道题要下一段大于这一段 所以的话我们就要记录每一段的状态 F[i,j]=F[j,k]+A[i] (j-i<=k-j, i<j<k)
然后我们可以优化一下 k是可以二分处理的 F[i,j]=F[j,k-n]+A[i] 然后就是树状数组优化一下 写到一半才发现可以写优先队列..
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #define Maxn 1010 using namespace std; bool Cmp(const pair<int,int> &x,const pair<int,int> &y){return x.first<y.first;} pair<int,int>pr[Maxn]; int tr[Maxn][Maxn]; int low_bit(int x){return x&(-x);} int N; void Add(int k,int x,int c){while(x<=N) {tr[k][x]=max(tr[k][x],c); x+=low_bit(x);}} int Find(int k,int x){int maxx=0; while(x>=1){maxx=max(maxx,tr[k][x]); x-=low_bit(x);} return maxx;} int twopart1(int x,int c) { int ret=-1; int L=x; int R=N; while(L<=R) { int mid=(L+R)>>1; if(pr[mid].first-pr[x].first>=c) R=mid-1,ret=mid; else L=mid+1; } return ret; } int twopart2(int x,int c) { int ret=-1; int L=1; int R=x; while(L<=R) { int mid=(L+R)>>1; if(pr[x].first-pr[mid].first>=c) L=mid+1,ret=mid; else R=mid-1; } return ret; } int main() { scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%d%d",&pr[i].first,&pr[i].second); sort(pr+1,pr+N+1,Cmp); memset(tr,0,sizeof(tr)); int Maxx=0; for(int i=1;i<=N;i++) for(int j=i+1;j<=N;j++) Add(i,N-j+1,pr[i].second+pr[j].second),Maxx=max(Maxx,Find(i,N-j+1)); for(int i=N;i>=1;i--) { for(int j=i+1;j<=N;j++) { int k=twopart1(j,pr[j].first-pr[i].first); if(k!=-1) Add(i,N-j+1,Find(j,N-k+1)+pr[i].second); Maxx=max(Maxx,Find(i,N-j+1)); } } memset(tr,0,sizeof(tr)); for(int i=1;i<=N;i++) for(int j=1;j<i;j++) Add(i,j,pr[i].second+pr[j].second),Maxx=max(Maxx,Find(i,j)); for(int i=1;i<=N;i++) { for(int j=1;j<i;j++) { int k=twopart2(j,pr[i].first-pr[j].first); if(k!=-1) Add(i,j,Find(j,k)+pr[i].second); Maxx=max(Maxx,Find(i,j)); } } return printf("%d\n",Maxx),0; } /* 6 5 6 1 1 10 5 7 6 4 8 8 10 */
原文：http://www.cnblogs.com/wohenshuai/p/5886596.html
