频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu 1025(最大上升子序列的n*logn解法)
2013-05-20 10:10:13           
收藏   我要投稿

之前遇到过这个算法,但是当时没有特别注意。

算法理解了七八分,但是还不够彻底,先把代码发出来,明天修改一下,附上完整的算法思路。


[cpp]
#include<stdio.h>  
#define N 500005  
int a[N],ans[N]; 
int main() 

    int n; 
    int x,y; 
    int i; 
    int count; 
    count=1; 
    while(scanf("%d",&n)!=EOF) 
    { 
        for(i=0;i<n;i++) 
        { 
            scanf("%d%d",&x,&y); 
            a[x]=y; 
        } 
        ans[1]=a[1]; 
        int ln; 
        ln=1; 
        for(i=2;i<=n;i++) 
        { 
            int low,up; 
            low=1; 
            up=ln; 
            while(low<=up) 
            { 
                int mid; 
                mid=(low+up)/2; 
                if(ans[mid]<a[i]) 
                    low=mid+1; 
                else 
                    up=mid-1; 
            } 
            ans[low]=a[i]; 
            if(low>ln) 
                ln++; 
        } 
        printf("Case %d:\n",count++); 
        if(ln==1) 
            printf("My king, at most 1 road can be built.\n"); 
        else 
            printf("My king, at most %d roads can be built.\n",ln); 
        printf("\n"); 
    } 
    return 0; 

#include<stdio.h>
#define N 500005
int a[N],ans[N];
int main()
{
 int n;
 int x,y;
 int i;
 int count;
 count=1;
 while(scanf("%d",&n)!=EOF)
 {
  for(i=0;i<n;i++)
  {
   scanf("%d%d",&x,&y);
   a[x]=y;
  }
  ans[1]=a[1];
  int ln;
  ln=1;
  for(i=2;i<=n;i++)
  {
   int low,up;
   low=1;
   up=ln;
   while(low<=up)
   {
    int mid;
    mid=(low+up)/2;
    if(ans[mid]<a[i])
     low=mid+1;
    else
     up=mid-1;
   }
   ans[low]=a[i];
   if(low>ln)
    ln++;
  }
  printf("Case %d:\n",count++);
  if(ln==1)
   printf("My king, at most 1 road can be built.\n");
  else
   printf("My king, at most %d roads can be built.\n",ln);
  printf("\n");
 }
 return 0;
}

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 升子 解法 序列
上一篇:冒泡排序与选择排序的递归实现
下一篇:九度OJ 1021 统计字符
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站