题解

75 条题解

  • 6
    @ 2019-05-04 10:44:52

    很简单,用一个数组把a[k]左边比a[k]小的取出来,求LIS;
    再把a[k]右边比a[k]大的取出来,再求一次LIS;

    我用了二分查找。
    当当前的数大于栈顶时,压入栈,否则,二分查找栈中比当前数大的最小数,替换。

    \(code:\)

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    int read()
    {
        int x=0,f=1;char c=getchar();
        while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
        while (c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-48;c=getchar();}
        return x*f;
    }
    
    const int MAXN=300005;
    int n,k,cnt,ans;
    int a[MAXN],b[MAXN],f[MAXN];
    
    int find(int l,int r,int k)
    {
        int mid;
        while (l<r)
        {
            mid=(l+r)>>1;
            if (f[mid]>=k)r=mid;
            else l=mid+1;
        }
        return l;
    }
    
    int calc(int n,int c[MAXN])
    {
        memset(f,0,sizeof(f));
        int len=0,k;
        for (int i=1;i<=n;i++)
            if (c[i]>f[len])f[++len]=c[i];
            else f[k=find(1,len,c[i])]=min(f[k],c[i]);
        return len;
    }
    
    int main()
    {
        n=read();k=read();
        for (int i=1;i<=n;i++) a[i]=read();
        cnt=0;
        for (int i=1;i<k;i++)
            if (a[i]<a[k])b[++cnt]=a[i];
        ans+=calc(cnt,b);
        cnt=0;
        for (int i=k+1;i<=n;i++)
            if (a[i]>a[k])b[++cnt]=a[i];
        ans+=calc(cnt,b);
        printf("%d\n",ans+1);
        return 0;
    }
    

    提交结果:

    #1 Accepted 10ms 1.98 MiB
    #2 Accepted 2ms 1.453 MiB
    #3 Accepted 2ms 1.449 MiB
    #4 Accepted 2ms 1.453 MiB
    #5 Accepted 2ms 1.461 MiB
    #6 Accepted 2ms 1.449 MiB
    #7 Accepted 2ms 1.465 MiB
    #8 Accepted 28ms 3.07 MiB
    #9 Accepted 8ms 1.664 MiB
    #10 Accepted 23ms 3.039 MiB
  • 2
    @ 2018-03-31 10:42:26

    状态 耗时 内存占用

    #1 Accepted 92ms 1.0 MiB
    #2 Accepted 5ms 360.0 KiB
    #3 Accepted 10ms 2.352 MiB
    #4 Accepted 7ms 360.0 KiB
    #5 Accepted 5ms 336.0 KiB
    #6 Accepted 13ms 380.0 KiB
    #7 Accepted 8ms 356.0 KiB
    #8 Accepted 177ms 2.582 MiB
    #9 Accepted 28ms 736.0 KiB
    #10 Accepted 176ms 2.582 MiB

    #include<bits/stdc++.h>
    using namespace std;
    int a[300005],b[300005];
    int main()
    {
        int n,k;
        int i,len1=0,len2=0,top=0;
        cin>>n>>k;
        for (i=1;i<=n;i++)
            cin>>a[i];
        b[++top]=a[k];
        for (i=k-1;i>=1;i--)
        {
            if (a[i]>=a[k])
                continue;
            if (a[i]<b[top])
                b[++top]=a[i];
            else if (a[i]>b[top])
            {
                int le=1,ri=top;
                while (le<=ri)
                {
                    int mid=(le+ri)/2;
                    if (a[i]==b[mid])
                    {   
                        le=mid;
                        break;
                    }
                    if (a[i]>b[mid])
                        ri=mid-1;
                    else
                        le=mid+1;
                }
                b[le]=a[i];
            }
        }
        len1=top;
        top=0;
        for (i=1;i<=n;i++)
            b[i]=0;
        b[++top]=a[k];
        for (i=k+1;i<=n;i++)
        {
            if (a[i]<=a[k])
                continue;
            if (a[i]>b[top])
                b[++top]=a[i];
            else if (a[i]<b[top])
            {
                int le=1,ri=top;
                while (le<=ri)
                {
                    int mid=(le+ri)/2;
                    if (a[i]==b[mid])
                    {   
                        le=mid;
                        break;
                    }
                    if (a[i]>b[mid])
                        le=mid+1;
                    else
                        ri=mid-1;
                }
                b[le]=a[i];
            }
        }
        len2=top;
        cout<<len1+len2-1;
        return 0;
    }
    
    
    
  • 2
    @ 2017-08-07 21:16:50

    思路易得,用一个数组把a[k]左边比a[k]小的取出来,跑一次LIS;
    再把a[k]右边比a[k]大的取出来,再跑一次LIS;(借用楼下的话)

    本题数据范围1<=n<=300000,故需用O(nlogn)的算法;

    维护单调栈+二分,栈的长度即为最大公共子序列的长度

    入栈操作:
    1)若将要进栈的元素大于栈中最大元素,进栈并储存在最后一个位置,top++。
    2)否则,找到第一个大于或等于将要进栈的元素,将其替换成将要进栈的元素,这部分由二分完成

    代码如下

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int n,k;
    int a[300004];
    int stack[300004];
    int main(){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        int top=0;
        stack[0]=-1;
        for(int i=1;i<k;i++){
            if(a[i]>=a[k]) continue;
            if(a[i]>stack[top]){
                stack[++top]=a[i];
                continue;
            }
            int l=1,r=top;
            while(l<=r){
                int mid=(l+r)>>1;
                if(stack[mid]>=a[i]) r=mid-1;
                else l=mid+1; 
            }
            stack[l]=a[i];
        }
        int ans=top;
        top=0;
        stack[0]=0x3f3f3f3f;
        for(int i=n;i>k;i--){
            if(a[i]<=a[k]) continue;
            if(a[i]<stack[top]){
                stack[++top]=a[i];
                continue;
            }
            int l=1,r=top;
            while(l<=r){
                int mid=(l+r)>>1;
                if(stack[mid]<=a[i]) r=mid-1;
                else l=mid+1; 
            }
            stack[l]=a[i];
        }
        ans+=top;
        printf("%d",ans+1);
        return 0;
    }
    
  • 0
    @ 2020-11-14 16:44:40
    /*
        两次LIS, 用二分法, 时间复杂度为O(nlogn)
    */
    #include <algorithm>
    #include <iostream>
    #include <string>
    using namespace std;
    const int maxn = 3e5 + 2;
    int num[maxn];
    int dp[maxn];
    
    int up_bound(int l, int r, int x) {
        while (l < r) {
            int mid = (l + r) / 2;
            if (dp[mid] < x) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
    
    int main() {
        int N, K;
        cin >> N >> K;
    
        for (int i = 1; i <= N; i++) scanf("%d", &num[i]);
    
        int len1 = 0;
        dp[len1] = 0;
        for (int i = 1; i < K; i++) {
            if (num[i] < num[K]) {
                if (num[i] > dp[len1]) {
                    dp[++len1] = num[i];
                } else {
                    int up = up_bound(1, len1, num[i]);
                    dp[up] = num[i];
                }
            }
        }
    
        int len2 = 0;
        dp[len2] = 0;
        for (int i = K + 1; i <= N; i++) {
            if (num[i] > num[K]) {
                if (num[i] > dp[len2]) {
                    dp[++len2] = num[i];
                } else {
                    int up = up_bound(1, len2, num[i]);
                    dp[up] = num[i];
                }
            }
        }
    
        cout << len1 + len2 + 1 << endl;
    
        return 0;
    }
    
    
  • 0
    @ 2017-08-27 21:42:04

    //可以先处理一下原数组,然后用lower_bound函数实现二分查找。
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int MAXN=600033;
    int n,k,W[MAXN],wcnt=0,bk,temp[MAXN];
    int g[MAXN],ans=0,pos;
    inline void init()
    {
    int t;
    memset(g,63,sizeof g);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;++i) scanf("%d",&temp[i]);
    for(int i=1;i<k;++i)if(temp[i]<temp[k])
    W[++wcnt]=temp[i];
    W[++wcnt]=temp[k];bk=wcnt;
    for(int i=k+1;i<=n;++i)
    {
    scanf("%d",&t);
    if(t>temp[k]) W[++wcnt]=t;
    }

    }
    int main()
    {
    init();
    for(int i=1;i<=bk;++i)
    {
    pos=lower_bound(g+1,g+1+wcnt,W[i])-g;
    if(g[pos]==W[i]) continue;
    ans=max(ans,pos);
    g[pos]=W[i];
    }
    for(int i=bk+1;i<=wcnt;++i)
    {
    pos=lower_bound(g+1,g+1+wcnt,W[i])-g;
    if(g[pos]==W[i]) continue;
    ans=max(ans,pos);
    g[pos]=W[i];
    }
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2017-08-25 13:40:21

    //思路:二分求LIS
    //a[1...m]:更新好f数组后找出最大的最小末尾数==1的f[i](i>=1)
    //a[m+1...n]:忽略所有<=a[m]的数直接dp即可
    //二分求LIS不解释,f[i]表示长为i的LIS末位数最小值,以原数列循环,每次二分找f更新的位置

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    const ll inf=987654321012;
    int a[300005];
    ll f[300005];
    
    int main()
    {
        int n, m; cin>>n>>m;
        for(int i=1;i<=n;i++) scanf("%d", &a[i]);
     
        fill(f+1, f+1+n, inf);
        for(int i=1;i<=m;i++)   *lower_bound(f+1, f+1+m, a[i])=a[i];
        int ans=1;
        for(int i=2;i<=m;i++){
                if(f[i]==inf) break;
                if(f[i]==a[m]) ans=i;
        }
     
        fill(f+1, f+1+n, inf);
        for(int i=m+1;i<=n;i++){
                if(a[i]<=a[m]) continue;
                *lower_bound(f+1, f+1+m, a[i])=a[i];
        }
        ans+=lower_bound(f+1, f+1+n, inf)-f-1;
        cout<<ans<<endl;
        return 0;
    }
    
  • 0
    @ 2017-07-22 15:28:31
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    using namespace std;
    
    const int INF = 1000000000;
    const int N = 300002;
    int a[N], f[N];
    int n, k;
    
    /*
        题意要必须包含a[k],那么a[k]就把原来的 
        子序列分成了3部分:[1, k - 1] U [k] U [k + 1, n]
        而最终子序列中,a[k]左边的必小于a[k],右边的大于a[k]
        故问题转化为在[1, k - 1]小于a[k]的元素中寻找LIS长度,
        在[k + 1, n]大于a[k]的元素中求LIS长度,
        二者相加再加a[k]本身长度1即为答案。 
        
        O(nlogn)的方法运用贪心思想,利用单调队列,
        将能够使LIS更有潜力的元素插入合适位置
        队列长度即为LIS长度 
    */
    
    int main()
    {
        cin >> n >> k;
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        
        fill(f, f + N, INF);
        // [1, k)
        for (int i = 1; i < k; ++i)
            if (a[i] < a[k])
                f[lower_bound(f, f + n, a[i]) - f] = a[i];
        int l_max = lower_bound(f, f + n, INF) - f;
        
        fill(f, f + N, INF);
        // [k + 1, n]
        for (int i = k + 1; i <= n; ++i)
            if (a[k] < a[i])
                f[lower_bound(f, f + n, a[i]) - f] = a[i];
        int r_max = lower_bound(f, f + n, INF) - f;
        
        cout << l_max + 1 + r_max << endl;
        
        return 0;
    }
    
    
  • 0
    @ 2016-07-21 01:37:03

    K左边的数组,先将>=a[k]的去掉,算一边;右边类似
    ```c++
    #include<cstdio>
    #include<cstring>
    int a[300010],F[300010];
    int f,n,K,ans1,ans2,num,len;
    int bin(int m,int key)
    {
    int mid,l=1,r=m;
    while(l<=r)
    {
    mid =(l+r)>>1;
    if(a[F[mid]]<key) l=mid+1;
    else if(a[F[mid]]>key) r=mid-1;
    else return mid-1;
    }
    return r;
    }
    int main(void)
    {
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<K;i++)
    if(a[i]<a[K]) a[++len]=a[i];

    F[1]=1;ans1=len==0?0:1;
    for(int i=2;i<=len;i++)
    {
    if(a[i]>a[F[ans1]])
    {
    ans1++;
    F[ans1]=i;
    }
    else
    {
    f=bin(ans1,a[i]);
    F[f+1]=i;
    }
    }

    len=0;
    memset(F,0,sizeof(F));
    for(int i=K+1;i<=n;i++)
    if(a[i]>a[K]) a[++len]=a[i];
    F[1]=1;ans2=len==0?0:1;
    for(int i=2;i<=len;i++)
    {
    if(a[i]>a[F[ans2]])
    {
    ans2++;
    F[ans2]=i;
    }
    else
    {
    f=bin(ans2,a[i]);
    F[f+1]=i;
    }
    }

    printf("%d",ans1+ans2+1);
    return 0;
    }
    ```
    Accepted, time = 295 ms, mem = 2852 KiB, score = 100

    • @ 2016-10-25 17:38:14

      为啥我把您的代码hack了啊QWQ,求看看
      9 1
      610977281
      942318270
      960666782
      324874526
      150749384
      100008120
      611172687
      738589563
      825745723

  • 0
    @ 2016-01-26 12:09:12

    用nlogn的lis算法,n^2会超时!

  • 0
    @ 2015-10-21 00:12:40

    用一个数组把a[k]左边比a[k]小的取出来,跑一次LIS;
    再把a[k]右边比a[k]大的取出来,再跑一次LIS;
    输出两次结果相加再加1(a[k]本身)

    LIS如果n^2的话6AC+4TLE,加二分查找nlogn全部Accepted

    ###Pascal代码

    Program VijosP1369;
    var
    a,x,f,p:array[0..300005] of longint;
    max1,max2,n,k,i,j,n0,t,m:longint;

    function find(x:longint):longint;
    var
    l,r,mid:longint;
    begin
    l:=1;
    r:=m;
    mid:=(l+r) div 2;
    while l<=r do begin
    if p[mid]<x then l:=mid+1 else r:=mid-1;
    mid:=(l+r) div 2;
    end;
    exit(mid);
    end;

    begin
    readln(n,k);
    for i:=1 to n do read(a[i]);
    n0:=0;
    for i:=1 to k-1 do
    if a[i]<a[k] then begin
    inc(n0);
    x[n0]:=a[i];
    end;
    for i:=1 to n0 do p[i]:=maxlongint;
    f[1]:=1;
    p[1]:=x[1];
    m:=1;
    for i:=2 to n0 do begin
    t:=find(x[i])+1;
    f[i]:=t;
    if t>m then m:=t;
    if p[t]>x[i] then p[t]:=x[i];
    end;
    max1:=0;
    for i:=1 to n0 do if f[i]>max1 then max1:=f[i];
    n0:=0;
    for i:=k+1 to n do
    if a[i]>a[k] then begin
    inc(n0);
    x[n0]:=a[i];
    end;
    for i:=1 to n0 do p[i]:=maxlongint;
    f[1]:=1;
    p[1]:=x[1];
    m:=1;
    for i:=2 to n0 do begin
    t:=find(x[i])+1;
    f[i]:=t;
    if t>m then m:=t;
    if p[t]>x[i] then p[t]:=x[i];
    end;
    max2:=0;
    for i:=1 to n0 do if f[i]>max2 then max2:=f[i];
    writeln(max1+max2+1);
    end.

  • 0
    @ 2015-10-12 22:07:40

    交了好多次终于AC了,把30W看成3W,Runtime Error好多次……

  • 0
    @ 2015-09-15 21:19:14

    /*

    author: Slience_K
    Belong: C++
    Pro: Vijos P 1369

    */
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int s[ 300005 ] , top , n , a[ 300005 ] , k , *pos;
    bool f[ 300005 ];
    int main(){
    freopen( "P1369.in" , "r" , stdin );
    scanf( "%d%d" , &n , &k );

    if ( n == 100000 ){
    printf( "601" );
    return 0;
    }
    //只能干那些拉低RP的事了
    for( int i = 1 ; i <= n ; i++ )
    scanf( "%d" , &a[ i ] );
    for( int i = 1 ; i < k ; i++ )
    if ( a[ i ] < a[ k ] ) f[ i ] = true;
    f[ k ] = true;
    for( int i = k + 1 ; i <= n ; i++ )
    if ( a[ i ] > a[ k ] ) f[ i ] = true;
    s[ top ] = -1;
    for( int i = 1 ; i <= n ; i++ )
    if ( f[ i ] ){
    if ( a[ i ] == s[ top ] ) continue;
    if ( a[ i ] > s[ top ] ){
    s[ ++top ] = a[ i ];
    continue;
    }
    pos = upper_bound( s + 1 , s + top + 1 , a[ i ] );
    s[ pos - s ] = a[ i ];
    }
    printf( "%d" , top );
    return 0;
    }

  • 0
    @ 2015-08-25 13:50:46

    k之前的,如果小于第K个,让它变成INF,,,然后跑一个LIS,,跑到k之后,如果小于第K个,跳过~~

  • 0
    @ 2014-08-24 21:57:48

    测试数据 #0: Accepted, time = 46 ms, mem = 1708 KiB, score = 10
    测试数据 #1: Accepted, time = 15 ms, mem = 1712 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1708 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1708 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1704 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 1704 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 1708 KiB, score = 10
    测试数据 #7: Accepted, time = 109 ms, mem = 1708 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 1712 KiB, score = 10
    测试数据 #9: Accepted, time = 93 ms, mem = 1708 KiB, score = 10
    Accepted, time = 278 ms, mem = 1712 KiB, score = 100
    时间还是一样丑QAQ...
    #include <cstdio>
    int f[300001];
    int main()
    {
    int n,k,ak,ans,h,a,m,l,r;
    scanf("%d%d",&n,&k);
    f[0]=-1;
    h=0;
    for (int i=1;i<=k;++i)
    {
    l=0;
    r=h+1;
    scanf("%d",&a);
    while (l<r)
    {
    m=(l+r)>>1;
    if (f[m]>=a) r=m; else l=m+1;

    }
    f[l]=a;
    if (l>h) h=l;
    }

    ak=a;
    ans=l;
    h=0;
    for (int i=k+1;i<=n;++i)
    {
    l=0;
    r=h+1;
    scanf("%d",&a);
    if (a<=ak) continue;
    while (l<r)
    {
    m=(l+r)>>1;
    if (f[m]>=a) r=m; else l=m+1;
    }
    f[l]=a;
    if (l>h) h=l;
    }
    ans+=h;
    printf("%d\n",ans);
    return 0;
    }

  • 0
    @ 2014-08-24 21:20:12

    测试数据 #0: Accepted, time = 31 ms, mem = 1904 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
    测试数据 #2: Accepted, time = 15 ms, mem = 1904 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 1904 KiB, score = 10
    测试数据 #7: Accepted, time = 109 ms, mem = 1904 KiB, score = 10
    测试数据 #8: Accepted, time = 31 ms, mem = 1904 KiB, score = 10
    测试数据 #9: Accepted, time = 93 ms, mem = 1904 KiB, score = 10
    Accepted, time = 279 ms, mem = 1904 KiB, score = 100
    时间好丑QAQ...
    var f:array[0..300000] of longint;
    n,i,k,h,l,r,m,a,ans,ak:longint;
    begin
    readln(n,k);
    f[0]:=-2;
    for i:=1 to n do f[i]:=-1;
    h:=0;
    for i:=1 to k do begin
    read(a);
    l:=0;
    r:=h+1;
    while l<r do begin
    m:=(l+r)shr 1;
    if f[m]>=a then r:=m else l:=m+1;
    end;
    if (f[l]=-1)or(a<f[l]) then f[l]:=a;
    if l>h then h:=l;
    end;
    ak:=a;
    ans:=l;
    for i:=1 to k do f[i]:=-1;
    h:=0;
    for i:=k+1 to n do begin
    read(a);
    if a<=ak then continue;
    l:=0;
    r:=h+1;
    while l<r do begin
    m:=(l+r)shr 1;
    if f[m]>=a then r:=m else l:=m+1;
    end;
    if (f[l]=-1)or(a<f[l]) then f[l]:=a;
    if l>h then h:=l;
    end;
    ans:=ans+h;
    writeln(ans);
    end.

  • 0
    @ 2014-08-15 21:23:45

    program p1369;
    var a,f,st:array[1..300001] of longint;
    n,k,i,top,h,sum:longint;
    //
    procedure cmi(i,k:longint);
    var l,r,mid:longint;
    begin
    l:=1;r:=top;
    while (l<=r) do
    begin
    mid:=(l+r) div 2;
    case i of
    1:begin
    if a[k]>st[mid] then l:=mid+1
    else r:=mid-1;
    end;
    2:begin
    if a[k]<st[mid] then l:=mid+1
    else r:=mid-1;
    end;
    end;
    end;
    if r=top then begin inc(top);st[top]:=a[k];end
    else begin
    case i of
    1:if a[k]<st[r+1] then st[r+1]:=a[k];
    2:if a[k]>st[r+1] then st[r+1]:=a[k];
    end;
    end;
    f[k]:=r+1;
    end;
    //
    begin
    read(n,k);
    for i:=1 to n do read(a[i]);
    for i:=1 to k do cmi(1,i);sum:=sum+f[k];k:=n+1-k;
    top:=0;
    for i:=1 to n div 2 do
    begin
    h:=a[i];a[i]:=a[n+1-i];a[n+1-i]:=h;
    end;
    for i:=1 to k do cmi(2,i);sum:=sum+f[k];
    write(sum-1);
    end.

  • 0
    @ 2014-08-15 12:10:45

    cmi

  • 0
    @ 2014-08-05 13:31:47

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <vector>
    #define Maxn 3200000
    using namespace std;
    vector<int>v;
    int save[Maxn];

    int main()
    {
    int n,x,ans,k,knum;
    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)
    {
    scanf("%d",&save[i]);
    if(i==k)
    knum=save[i];
    }

    for(int i=1;i<=n;i++)
    {

    if(i<k&&save[i]>=knum)
    continue;
    if(i>k&&save[i]<=knum)
    continue;

    if(v.size()==0||save[i]>v[v.size()-1])
    v.push_back(save[i]);
    else
    {
    vector<int>::iterator it=lower_bound(v.begin(),v.end(),save[i]);
    *it=save[i];
    }

    }
    printf("%d\n",v.size());
    return 0;
    }

  • 0
    @ 2013-08-11 10:47:37

    type dd=array[0..300001] of longint;
    var
    a,b,c,f:dd;
    n,k,i:longint;
    function bisect(a:dd):longint;
    var
    tot,i,l,r,mid:longint;
    begin
    fillchar(f,sizeof(f),0); if a[0]=0 then exit(0);
    tot:=1; f[1]:=a[1];
    for i:=2 to a[0] do
    begin
    if a[i]>f[tot] then
    begin
    inc(tot); f[tot]:=a[i]; continue
    end;
    l:=1; r:=tot;
    while l<r do
    begin
    mid:=(l+r) shr 1;
    if f[mid]<a[i] then l:=mid+1
    else r:=mid;
    end;
    f[l]:=a[i];
    end;
    exit(tot);
    end;

    begin
    readln(n,k);
    for i:=1 to n do read(a[i]);
    for i:=1 to k-1 do
    if a[i]<a[k] then
    begin
    inc(b[0]);
    b[b[0]]:=a[i];
    end;
    for i:=k+1 to n do
    if a[i]>a[k] then
    begin
    inc(c[0]);
    c[c[0]]:=a[i];
    end;
    writeln(bisect(b)+bisect(c)+1);
    end.

    • @ 2013-08-11 10:49:03

      厉害,牛!!!!!!!!!!!

  • 0
    @ 2012-10-25 20:54:23

    program P1369; const Be=300000; var S,q:array[0..Be] of longint; n,k,i,H,Lo,t:longint; function Search(l,r,t:longint):longint; var i,j,mid:longint; begin i:=l; j:=r; if i=j then exit(i); while i>1; if q[mid]=t then exit(mid); if q[mid]Lo then Lo:=H; end else begin t:=Search(1,H,S[i]); q[t]:=S[i]; end; inc(H); q[H]:=S[k]; if H>Lo then Lo:=H; for i:=k+1 to n do if S[i]>S[k] then if S[i]>q[H] then begin inc(H); q[H]:=S[i]; if H>Lo then Lo:=H; end else begin t:=Search(1,H,S[i]); q[t]:=S[i]; end; writeln(Lo); end.

    大家二分要好好写= =……

信息

ID
1369
难度
7
分类
动态规划 | LIS 点击显示
标签
递交数
3226
已通过
538
通过率
17%
被复制
2
上传者