/ Vijos / 题库 / 难解的问题 /

题解

75 条题解

  • 6
    @ 5 年前

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

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

    code: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;
}
    Copy

    提交结果：
    #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
    @ 7 年前

    状态 耗时 内存占用

    #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;
}
    Copy
  • 2
    @ 7 年前

    思路易得，用一个数组把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;
}
    Copy
  • 1
    @ 9 年前

    用一个数组把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
    @ 4 年前 
    /*
    两次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;
}
    Copy
  • 0
    @ 7 年前

    //可以先处理一下原数组，然后用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
    @ 7 年前

    //思路：二分求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;
}
    Copy
  • 0
    @ 7 年前 
    #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;
}
    Copy
  • 0
    @ 8 年前

    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

    • @ 8 年前

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

  • 0
    @ 9 年前

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

  • 0
    @ 9 年前

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

  • 0
    @ 9 年前

    /*

    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
    @ 9 年前

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

  • 0
    @ 10 年前

    测试数据 #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
    @ 10 年前

    测试数据 #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
    @ 10 年前

    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
    @ 10 年前

    cmi

  • 0
    @ 10 年前

    #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
    @ 11 年前

    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.

    • @ 11 年前

      厉害，牛！！！！！！！！！！！

  • 0
    @ 12 年前

    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 点击显示
标签
递交数
3264
已通过
542
通过率
17%
被复制
3
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1