首页 > 代码库 > [DP之普通系列]
[DP之普通系列]
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] 然后就是树状数组优化一下 写到一半才发现可以写优先队列..
![技术分享](/d/file/p/2024/07/06/4558cea76202f0f8d3a4af34d247d435.gif)
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<cstdlib>#define Maxn 1010using 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;}/*65 61 110 57 64 88 10*/
[DP之普通系列]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。