首页 > 代码库 > [DP之普通系列]

[DP之普通系列]

2024-08-13 23:26:43   209人阅读

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 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*/
View Code

 

[DP之普通系列]


联系
我们