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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1046】【HAOI2007】【上升序列】  

2014-03-12 16:37:55|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   单调栈,然后就这样...
   然后PE数次,发现此题是考虑行末空格的...
===================

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define maxn 10010
using namespace std;

int n,m,top,max,a[maxn],st[maxn],f[maxn];

int main()
{
    scanf("%d",&n);
    int i;
    memset(a,0,sizeof(a));
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    memset(f,0,sizeof(f));
    memset(st,0,sizeof(st));
    st[0]=0;st[1]=n;f[n]=1;top=1;max=1;a[0]=-1<<15;
    for (i=n-1;i>=1;i--){
      int l=0,r=top;
      while (l<r){
            int mid=(r+l+1)/2;
            if (a[st[mid]]>a[i]) l=mid;
                          else   r=mid-1;}
      f[i]=l+1;
      if (max<f[i]) max=f[i];
      if (top<l+1||a[st[l+1]]<a[i]){
            if (top==l)top++;
            st[l+1]=i;}}
    scanf("%d",&m);
    for (i=0;i<m;i++){
        int len;
        scanf("%d",&len);
        if (max<len) {printf("Impossible\n");continue;}
        int j,k=len,w=0;
        for (j=1;j<=n;j++)     
         if (f[j]>=k&&a[j]>a[w]){
          printf("%d",a[j]);
          w=j;k--;
          if (k) printf(" ");
          if (k==0) break;}
        printf("\n");}
    return 0;
}

  评论这张
 
阅读(33)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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