注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3594][Scoi2014]方伯伯的玉米田  

2015-03-21 23:50:55|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3594: [Scoi2014]方伯伯的玉米田

感觉第一次做二维数据结构+dp

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int K = 500+10;
const int V = 5500+10;
int tree[K][V],tmp[K],n,m,ans;
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
void push(int x,int y,int val){
for(x++;x<=m+1;x+=x&-x)
for(int yy=y;yy<=m+5000;yy+=yy&-yy)
tree[x][yy]=max(tree[x][yy],val);
}
int get(int x,int y){
int re=0;
for(x++;x;x-=x&-x)
for(int yy=y;yy;yy-=yy&-yy)
re=max(tree[x][yy],re);
return re;
}
int main(){
int i,j,a;
n = scan();m = scan();
for(i=1;i<=n;i++){
a = scan();
for(j=0;j<=m;j++)
ans = max(ans,tmp[j]=(get(j,a+j)+1));
for(j=0;j<=m;j++)
push(j,a+j,tmp[j]);
}
printf("%d\n",ans);
return 0;
}

题解:
显然每次+1最好是后缀操作
f[i][j]表示当前用了i次操作,最后一位是j的最大保留数
  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017