精华内容
下载资源
问答
  • 题目大意:求最长不上升子序列长度 and最长上升子序列长度 题目思路:使用lower_bound和upper_bound,以最长上升子序列举例,如果新来的元素大于目前维护的序列的最后一个元素,那就加进来,如果比他小,那么就用...

    题目链接:https://www.luogu.org/problem/P1020

     

    题目大意:求最长不上升子序列长度 and 最长上升子序列长度

     

    题目思路:使用lower_bound和upper_bound,以最长上升子序列举例,如果新来的元素大于目前维护的序列的最后一个元素,那就加进来,如果比他小,那么就用lower_bound获得第一个大于它的数字的位置,并代替它,之所以要用lower_bound是因为不能出现重复元素,这样就能保证想要得到的序列一定能尽可能长,但是要注意,最后得到的序列中的元素并不是真正的最长上升子序列,这种做法只能保证其长度保持正确。

    相反地,对于最长不上升子序列,需要找到的第一个小于它的位置,并换掉它,这里要用upper_bound,因为可以出现重复元素,如果把比小的变大能多多益善

     

    以下是代码:

    #include<bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define rep(i,a,b) for(ll i=a;i<=b;i++)
    #define per(i,a,b) for(ll i=a;i>=b;i--)
    #define ll long long
    const int MAXN = 1e5+5;
    const ll MOD =1e9+7;
    int a[MAXN];
    int dp1[MAXN],dp2[MAXN];
    int main(){
        int n=0;
        while(~scanf("%d",&a[++n]));
        n--;
        int len1=1,len2=1;
        dp1[1]=dp2[1]=a[1];
        rep(i,2,n){
            if(a[i]<=dp1[len1])dp1[++len1]=a[i];
            else{
                int pos=upper_bound(dp1+1,dp1+len1+1,a[i],greater<int>())-dp1;
                dp1[pos]=a[i];
            }
            if(a[i]>dp2[len2])dp2[++len2]=a[i];
            else{
                int pos=lower_bound(dp2+1,dp2+len2+1,a[i])-dp2;
                dp2[pos]=a[i];
            }
        }
        cout<<len1<<endl<<len2<<endl;
        return 0;
    }
    

     

    展开全文
  • 最长不上升子序列

    千次阅读 2013-09-23 20:35:34
    但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都能高于等于前一发的高度。某天,雷达捕捉到敌国导弹来袭。由于该系统还在试用阶段,所以只用一套系统,因此有可能...

    拦截导弹

    时间限制:3000 ms  |  内存限制:65535 KB
    难度:3
    描述

    某国为了防御敌国的导弹袭击,发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于等于前一发的高度。某天,雷达捕捉到敌国导弹来袭。由于该系统还在试用阶段,所以只用一套系统,因此有可能不能拦截所有的导弹。

    输入
    第一行输入测试数据组数N(1<=N<=10)
    接下来一行输入这组测试数据共有多少个导弹m(1<=m<=20)
    接下来行输入导弹依次飞来的高度,所有高度值均是大于0的正整数。
    输出
    输出最多能拦截的导弹数目
    样例输入
    2
    8
    389 207 155 300 299 170 158 65
    3
    88 34 65
    样例输出
    6
    2



    令A[i]表示输入第i个元素,D[i]表示从A[1]到A[i]中以A[i]结尾的最长子序列长度。对于任意的0 <  j <= i-1,如果A(j)>A(i),则A(i)可以接在A(j)后面形成一个以A(i)结尾的新的最长不上升子序列。对于所有的 0 <  j <= i-1,我们需要找出其中的最大值。

    DP状态转移方程:

    D[i] = max{1, D[j] + 1} (j = 1, 2, 3, ..., i-1 且 A[j] >A[i])

    解释一下这个方程,i, j在范围内:

    如果 A[j] > A[i] ,则D[i] = D[j] + 1

    如果 A[j] = <A[i] ,则D[i] = 1

    #include <iostream>
    #define SIZE 1001
     using namespace std;
     int main()
    {
        int i, j, n, max;
        /* a[i]表示输入第i个元素 */
        int a[SIZE];
        /* d[i]表示以a[i]结尾的最长子序列长度 */
        int d[SIZE];
     	int y;
    	cin>>y;
    	while(y--)
    	{
        cin >> n;
        for (i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
         max = 0;
        for (i = 1; i <= n; i++)
        {
            d[i] = 1;
            for (j = 1; j <= i - 1; j++)
            {
                if (a[j] > a[i] && d[i] < d[j] + 1)
                {
                    d[i] = d[j] + 1;
                }
            }
            /* 记录最长子序列 */
            if (d[i] > max) max = d[i];
        }
        cout << max << endl;
    	}
        return 0;
    }


    展开全文
  • 题目大意:让你求出这个串是否是近似有序串,什么叫做近似有序串呢,...如何求最大有序子串呢,就比较一下最长不上升子序列的长度和最长不下降子序列的长度,取最长的即可。 #include&lt;iostream&gt; #...

    题目大意:让你求出这个串是否是近似有序串,什么叫做近似有序串呢,就是,这个串去掉任意一个字符也能保持有序。

    算法思路:模板题,只需要求出最大的有序子串,然后看这个串总的长度-1是否小于等于最大有序子串的长度,如果不满足,则说明这个串不是近似串。如何求最大有序子串呢,就比较一下最长不上升子序列的长度和最长不下降子序列的长度,取最长的即可。

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    #define MAXN 100050
    #define INF 0x3f3f3f3f
    int t,a[MAXN],ans[MAXN],d[MAXN],S[MAXN],n;
    
    int BSearch(int x, int y, int v) //二分求上界(不上升)
    {
        while(x <= y)
        {
            int mid = x+(y-x)/2;
            if(S[mid] >= v) x = mid+1;
            else y = mid-1;
        }
        return x;
    }
    int BSearch2(int x, int y, int v) //二分求上界(不下降)
    {
        while(x <= y)
        {
            int mid = x+(y-x)/2;
            if(S[mid] <= v) x = mid+1;
            else y = mid-1;
        }
        return x;
    }
    
    int LIS()//最长不下降子序列
    {
        memset(d,0,sizeof(d));
        for(int i = 1; i <=n; i++) S[i] = INF;
        int res = 0;
       for(int i = 1; i <= n; i++)
        {
            int x = 1, y = i;
            int pos = BSearch2(x, y, a[i]);
            d[i] = pos;
            S[d[i]] = min(S[d[i]], a[i]);
            res = max(res, d[i]);
        }
        return res;
    }
    int LFS()//最长不上升子序列
    {
         for(int i = 1; i <=n; i++) S[i] = -INF; //注意初始值
        memset(d, 0, sizeof(d));
        int res = 0;
        for(int i = 1; i <= n; i++)
        {
            int x = 1, y = i;
            int pos = BSearch(x, y, a[i]);
            d[i] = pos;
            S[d[i]] = max(S[d[i]], a[i]);
           res = max(res, d[i]);
        }
        return res;
    }
    int main()
    {
    
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
    
            for(int i=1; i<=n; i++)
            {
                scanf("%d",&a[i]);
            }
    
            int len1=LIS();//nlogn
            int len2=LFS();//nlogn
    
            int flag=max(len1,len2);
    
            if(n-1<=flag)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
    
    
        }
    
    
    
        return 0;
    
    }

     这里顺便补充一下,最长上升子序列和最长下降子序列的模板,过几天就去比赛了,记录一下。

    
    #include<cstdio>
    #include<cstring>
    #define MAXN 40005
    
    int arr[MAXN],ans[MAXN],len;
    
    
    
    int binary_search(int i)
    {
        int left,right,mid;
        left=0,right=len;
        while(left<right)
        {
            mid = left+(right-left)/2;
            if(ans[mid]>=arr[i]) right=mid;
            else left=mid+1;
        }
        return left;
    }
    
    int main()
    {
       
        int T,p,i,j,k;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d",&p);
            for(i=1; i<=p; ++i)
                scanf("%d",&arr[i]);
    
            ans[1] = arr[1];
            len=1;
            for(i=2; i<=p; ++i)
            {
                if(arr[i]<ans[len]) //这个是求最长上升子序列,如果是求下降的话,改成小于号即可
                    ans[++len]=arr[i];
                else
                {
                    int pos=binary_search(i);   
                    ans[pos] = arr[i];
                }
    
            }
            printf("%d\n",len);
        }
    
        return 0;
    
    }
    
    

     

    展开全文
  • 最长上升子序列 即一串给定的数字中,(可以不连续但必须符合原定顺序)一个最长的上升数字子串。 最长不上升子串 同上,即小于等于 重点 此题用到了一种方法,即先将dp【1】=a【1】,之后开始一个一个查找后面的...

    最长上升子序列
    即一串给定的数字中,(可以不连续但必须符合原定顺序)一个最长的上升数字子串。

    最长不上升子串
    同上,即小于等于

    重点
    此题用到了一种方法,即先将dp【1】=a【1】,之后开始一个一个查找后面的数字,如果该数字小于等于(这是对最长不上升子串来说的,如果是最长上升子串则为大于)当前dp数组最后一位,则加入到最后面,如果该数字大于dp中最小的数字,则利用二分法插入,如此循环,dp的长度就是答案。
    (这是因为只有小于等于时dp数组长度才变化,其他情况只是在替换,让更多的数可以插进去)

    将我卡死了两小时的点
    在利用二分查找时可以使用STL中的函数,但我选择了手写,一定要注意求最长不上升子序列时要替换的是第一个小于a[i]的数字,如果这个被替换数字不在末尾,可能不会有什么大问题(其实还会有),但一旦在最后,那么你的最终答案就一定错了(极大概率),例如 5 3 这时要插入一个5 如果你找的是小于等于,像这样

    while(left<=right)
                {
                    if(dp[mid]<=a[i])
                        right=mid-1;
                    else
                        left=mid+1;
                    mid=(left+right)>>1;
                }
    

    那么5将会被换成5 但其实你需要把 3换成5 ,所以应该要这样

    while(left<=right)
                {
                    if(dp[mid]<a[i])
                        right=mid-1;
                    else
                        left=mid+1;
                    mid=(left+right)>>1;
                }
    

    一个等号之差便决定对错

    而在求最长上升子序列时也是如此,一定要找第一个大于等于a[i]的数字,例如1 2 3 你要插入一个2 如果找的是大于的 ,那么 就成了 1 2 2 显然不对,应当把2 替换成 2
    之后附上AC代码

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<stdio.h>
    using namespace std;
    int a[100005];
    int dp[100005];
    int dp2[100005];
    int main()
    {
        //freopen("D:\\test\\in.txt","r",stdin);
        int k=1;
        while(scanf("%d",&a[k])!=EOF)
            k++;
        k--;
        dp[1]=a[1];
        dp2[1]=a[1];
        int len=1;
        int len2=1;
        for(int i=2;i<=k;i++)
        {
            if(dp[len]>=a[i])
                dp[++len]=a[i];//cout<<"dp[len]:"<<dp[len-1]<<"a"<<a[i]<<endl;
            else
            {
                int left=1;
                int right=len;
                int mid=(left+right)>>1;
                while(left<=right)
                {
                    if(dp[mid]<a[i])
                        right=mid-1;
                    else
                        left=mid+1;
                    mid=(left+right)>>1;
                }
                //cout<<"dp"<<dp[left]<<endl;
                dp[left]=a[i];
                //cout<<"dp"<<a[i]<<endl;
            }
            if(dp2[len2]<a[i])
                dp2[++len2]=a[i];
            else
            {
                int left=1;
                int right=len2;
                int mid=(left+right)>>1;
                while(left<=right)
                {
                    if(dp2[mid]>=a[i])
                        right=mid-1;
                    else
                        left=mid+1;
                    mid=(left+right)>>1;
                }
                dp2[left]=a[i];
            }
        }
        cout<<len<<endl;
        cout<<len2<<endl;
       // fclose(stdin);
        return 0;
    }
    
    展开全文
  • 目录最长上升子序列一、朴素做法O(2n)O(2^n)O(2n)二、优化做法O(nlogn)O(nlogn)O(nlogn)三、例题引入:P1020 导弹拦截(求最长上升子序列和最长不上升子序列)1.朴素做法暴力O(n2)O(n^2)O(n2)2.树状数组优化O(nlogn)...
  • 拦截导弹 题目大意: 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后...第一个就是求最长不上升子序列的长度。 第二个是最
  • #include &lt;stdio.h&gt; #include &lt;stdlib.h&... //len为子问题:以i结尾的最长不上升子序列 int len[length+10]; for(int i = 0; i &lt; length; i++) len[i] ...
  • 这道题,其实要求的就是最长不上升子序列的长度以及最长上升子序列的长度。这个问题确定挺经典的。 从头开始讲吧。 一、lower_bound和upper_bound 先了解一下STL中的这两个函数的作用。 假设我们在一个有序数组a中...
  • 第一问,相当于求一个最长不上升子序列。 第二问,相当于求一个最长上升子序列 证明如下: 假设打导弹的方法是这样的:取任意一个导弹,从这个导弹开始将能打的导弹全部打完。而这些导弹全部记为为同一组,再在...
  • hdu 6197 ...既然删掉k个后不增或者不减,那么就先求数组的最长不下降子序列的长度l1和最长不上升子序列的长度l2,若l1>=n-k||l2>=n-k,则满足要求。 #include<iostream> #inclu...
  • 但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能能...
  • 但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能能...
  • 输入导弹依次飞来的高度(雷达给出的高度数据是大于30000 的正整数),计算这套系统最多能拦截多少导弹和如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 【输入样例】 389 207 155 300 299 170 158 65  ...
  • 不上升子序列的个数等于最长上升子序列的长度。 #include #include #include #include using namespace std; #define INF 9999999 int dp[10001]; int num[10001]; int num2[10001]; int tops; int dos(int x)
  • lower_bound(a,a+n,i)函数 返回从数组a到a+n中第一个>=i的元素地址 upper_bound(a,a+n,i)函数 返回从数组a到a+n中第一个>i的元素地址 #include<cstdio> #include<algorithm>......
  • LIS最长不上升子序列

    2018-09-07 20:21:25
    令给定数字序列(a 1,a 2,...,a N)的子序列为任何序列(a i 1,a i 2,...,a iK),其中1 &lt;= i 1 &lt; i 2 &lt;... &lt; i K &lt;= N.。例如,序列(1,7,3,5,9,4,8​...
  • 这道题分别是问我们最长不上升子序列和最长上升子序列的长度。根据数据范围,我们用二分+单调栈来维护。 代码如下: #include #include #include using namespace std ; const int N= 300000 ;...
  • lower_bound(begin,end,num):二分查找第一个大于等于num的数字 upper_bound(begin,end,num):二分查找第一个大于num的数字 lower_bound(begin,end,num,greater< type>()):二分查找第一个小于等于num的数字 ...
  • codevs-3955 最长不上升子序列

    千次阅读 2017-05-19 10:23:56
    给一个数组a1, a2 … an,找到最长上升子序列ab1#include "cctype" #include "cstdio" #include "cstring"#define max(a, b) ((a) > (b) ? (a) : (b))inline void readIn(unsigned int& x) { static char ch;
  • dp[i] 当下标为i时最大的子序列长度. O(n2)O(n^2)O(n2) //import java.util.Scanner; import java.util.*; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in...
  • 但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,并观测到导弹依次飞来的高度,请计算这套系统最多能拦截多少...
  • 这种问题一般都比较熟悉,我们先看n^2的...但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意 的高度,但是以后每一发炮弹都能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还...
  • 经过1111年的韬光养晦,某国研发出了一种新的导弹拦截系统,凡是与它的距离超过其工作半径的导弹都能够被它成功拦截。当工作半径为00时,则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷:每...
  • 第一问:没什么好说的,基础的线性dp求解经典的最少不上升(下降)子序列; 第二问:贪心思想。 需要n个导弹就想当于把一串数字划分为n个部分,且每个部分都是一段递减的子序列 例如 :6 5 1 7 3 2 需要最少的炮弹–...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,620
精华内容 1,048
关键字:

最长不上升子序列