hdu 5421 小明系列问题——小明序列(LIS最长上升子序列)

 1 /*****************************************************
 2 题目:     小明系列问题——小明序列(hdu 4521)
 3 链接:     http://acm.hdu.edu.cn/showproblem.php?pid=4521
 4 算法:     LIS最长上升子序列
 5
 6 ******************************************************/
 7 #include<cstdio>
 8 #include<cstring>
 9 #include<algorithm>
10 #include<iostream>
11 #include<queue>
12 using namespace std;
13
14 const int mx=100005;
15 int d[mx],dp[mx],a[mx];
16 queue<int>q;
17
18 int BinSerch(int l,int r,int cut)
19 {
20     while (l<=r)
21     {
22         int m=(l+r)>>1;
23         if (cut>d[m]&&cut<=d[m+1]) return m;
24         if (cut>d[m]) l=m+1;
25         else r=m-1;
26     }
27     return 0;
28 }
29
30 int LIS(int n,int k)
31 {
32     int len=1,j;
33     fill(d,d+n+3,mx);
34     d[1]=a[0];
35     for (int i=k+1;i<n;i++)
36     {
37         if (a[i]>d[len]) j=len+1;
38         else j=BinSerch(1,len,a[i])+1;
39         dp[i]=j;
40         q.push(i);
41
42         int cut=q.front();
43
44         q.pop();
45         d[dp[cut]]=min(a[cut],d[dp[cut]]);
46         len=max(len,dp[cut]);
47     }
48     while (!q.empty())
49     {
50         int cut=q.front();
51         q.pop();
52         len=max(len,dp[cut]);
53     }
54     return len;
55 }
56
57 int main()
58 {
59     int n,d;
60     while (~scanf("%d%d",&n,&d))
61     {
62         while (!q.empty()) q.pop();
63         for (int i=0;i<n;i++) scanf("%d",&a[i]);
64         for (int i=1;i<=d;i++)
65         {
66             dp[i]=1;
67             q.push(i);
68         }
69         printf("%d\n",LIS(n,d));
70     }
71 }
时间: 07-29

hdu 5421 小明系列问题——小明序列(LIS最长上升子序列)的相关文章

hdu 4521 小明系列问题——小明序列 (间隔至少为d的LIS 两种解法)

先附上资源地址:http://www.ruanyifeng.com/blog/2013/04/processes_and_threads.html 进程(process)和线程(thread)是操作系统的基本概念,但是它们比较抽象,不容易掌握. 最近,我读到一篇材料,发现有一个很好的类比,可以把它们解释地清晰易懂. 1. 计算机的核心是CPU,它承担了所有的计算任务.它就像一座工厂,时刻在运行. 2. 假定工厂的电力有限,一次只能供给一个车间使用.也就是说,一个车间开工的时候,其他车间都必须停工

hdu 4521 小明系列问题——小明序列 线段树+二分

小明系列问题——小明序列 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Problem Description 大家都知道小明最喜欢研究跟序列有关的问题了,可是也就因为这样,小明几乎已经玩遍各种序列问题了.可怜的小明苦苦地在各大网站上寻找着新的序列问题,可是找来找去都是自己早已研究过的序列.小明想既然找不到,那就自己来发明一个新的序列问题吧!小明想啊想,终于想出了一个新的序列

HDU 4521 小明系列问题——小明序列 (LIS加强版)

小明系列问题——小明序列 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 1946    Accepted Submission(s): 596 Problem Description 大家都知道小明最喜欢研究跟序列有关的问题了,可是也就因为这样,小明几乎已经玩遍各种序列问题了.可怜的小明苦苦地在各大网站上寻找着新的序列问题, 可是找来找

hdu 4521 小明系列问题——小明序列(线段树+DP或扩展成经典的LIS)

小明系列问题--小明序列 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1553    Accepted Submission(s): 457 Problem Description 大家都知道小明最喜欢研究跟序列有关的问题了,但是也就由于这样,小明差点儿已经玩遍各种序列问题了.可怜的小明苦苦地在各大站点上寻找着新的序列问题,但是找来

hdu 4521 小明系列问题——小明序列 (LIS变形)

小明系列问题--小明序列 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1848    Accepted Submission(s): 564 Problem Description 大家都知道小明最喜欢研究跟序列有关的问题了,可是也就因为这样,小明几乎已经玩遍各种序列问题了.可怜的小明苦苦地在各大网站上寻找着新的序列问题,可是找来找

小明系列问题――小明序列(LIS)

小明系列问题――小明序列 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Practice HDU 4521 Description 大家都知道小明最喜欢研究跟序列有关的问题了,可是也就因为这样,小明几乎已经玩遍各种序列问题了.可怜的小明苦苦地在各大网站上寻找着新的序列问题,可是找来找去都是自己早已研究过的序列.小明想既然找不到,那就自己来发明一个新的序列问题吧!

小明系列问题——小明序列

hdu4521:http://acm.hdu.edu.cn/showproblem.php?pid=4521 题解:给你一个序列,然后让你找一个最长上升子序列,但是这个最长上升子序列的数在原来序列的间隔不少于d. 题解:如果没有d的要求就是一个求最长上升子序列.这里用线段树可以来优化.以数的值来建树.维护一个sum值,num[rt].sum表示以rt值结尾的最长上升子序列的长度.同时f[i]表示以第i个数结尾的最长上升子序列的长度.对于d,我们只要再算第i个数的时候,只更新了前1到i-d-1个数

hdu4521 小明系列问题——小明序列(LIS变种 (线段树+单点更新解法))

链接: huangjing 题目:中文题目 思路: 这个题目如果去掉那个距离大于d的条件,那么必然是一个普通的LIS,但是加上那个条件后就变得复杂了.用dp的解法没有看懂,我用的线段树的解法...就是采用延迟更新的做法,用为距离要大于d啊,所以我们在循环到第i的时候,就对(i-d-1)这个点进行更新,因为如果在(i-d-1)这个点更新了,会对后面的造成影响,然后线段树的tree[]数组存的是以i结尾的最长lis,那么每次询问的时候就找最大的tree[]就可以了... 代码: 小明系列问题--小明

hdu45221——小明系列问题——小明序列 线段树优化dp

小明系列问题--小明序列 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1918    Accepted Submission(s): 583 Problem Description 大家都知道小明最喜欢研究跟序列有关的问题了,可是也就因为这样,小明几乎已经玩遍各种序列问题了.可怜的小明苦苦地在各大网站上寻找着新的序列问题,可是找来找