题解

44 条题解

  • 2
    @ 2018-04-20 12:40:03

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxx=666;
    int main()
    {
    int n;
    cin>>n;
    while(n--)
    {
    int f[maxx]={0},maxy,ans=0,m1,m2,a[maxx],b[maxx];
    cin>>m1;
    for(int i=0;i<m1;i++)
    cin>>a[i];
    cin>>m2;
    for(int i=0;i<m2;i++)
    cin>>b[i];
    for(int i=0;i<m1;i++)
    {
    maxy=0;
    for(int j=0;j<m2;j++)
    {
    if(a[i]>b[j]&&maxy<f[j])
    maxy=f[j];
    if(a[i]==b[j])
    f[j]=maxy+1;
    }
    }
    for(int i=0;i<m2;i++)
    {
    ans=max(ans,f[i]);
    }
    cout<<ans<<endl;
    }
    return 0;
    }

  • 2
    @ 2015-09-15 20:38:18

    /*

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

    */
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int T , n , m , maxn , f[ 505 ] , a[ 505 ] , b[ 505 ];
    int main(){
    freopen( "P1264.in" , "r" , stdin );
    scanf( "%d" , &T );
    for( int l = 1 ; l <= T ; l++ ){
    memset( f , 0 , sizeof( f ) );
    scanf( "%d" , &n );
    for( int i = 1 ; i <= n ; i++ )
    scanf( "%d" , &a[ i ] );
    scanf( "%d" , &m );
    for( int i = 1 ; i <= m ; i++ )
    scanf( "%d" , &b[ i ] );
    for( int i = 1 ; i <= n ; i++ ){
    maxn = 0;
    for( int j = 1 ; j <= m ; j++ )
    if ( b[ j ] < a[ i ] ) maxn = max( maxn , f[ j ] );
    else if ( b[ j ] == a[ i ] ) f[ j ] = max( f[ j ] , maxn + 1 );
    }
    maxn = 0;
    for( int i = 1 ; i <= m ; i++ )
    maxn = max( maxn , f[ i ] );
    printf( "%d\n" , maxn );
    }
    return 0;
    }

  • 1
    @ 2023-06-21 15:52:21
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxx=666;
    int main()
    {
    int n;
    cin>>n;
    while(n--)
    {
    int f[maxx]={0},maxy,ans=0,m1,m2,a[maxx],b[maxx];
    cin>>m1;
    for(int i=0;i<m1;i++)
    cin>>a[i];
    cin>>m2;
    for(int i=0;i<m2;i++)
    cin>>b[i];
    for(int i=0;i<m1;i++)
    {
    maxy=0;
    for(int j=0;j<m2;j++)
    {
    if(a[i]>b[j]&&maxy<f[j])
    maxy=f[j];
    if(a[i]==b[j])
    f[j]=maxy+1;
    }
    }
    for(int i=0;i<m2;i++)
    {
    ans=max(ans,f[i]);
    }
    cout<<ans<<endl;
    }
    return 0;
    }
    
  • 1
    @ 2015-10-17 22:23:39

    P1264神秘的咒语Accepted
    记录信息
    评测状态 Accepted
    题目 P1264 神秘的咒语
    递交时间 2015-10-17 22:20:42
    代码语言 C++
    评测机 VijosEx
    消耗时间 111 ms
    消耗内存 540 KiB
    评测时间 2015-10-17 22:20:43
    评测结果
    编译成功

    foo.cpp: In function 'int main()':
    foo.cpp:17:45: warning: unknown conversion type character 'l' in format [-Wformat=]
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    ^
    foo.cpp:17:45: warning: too many arguments for format [-Wformat-extra-args]
    foo.cpp:19:45: warning: unknown conversion type character 'l' in format [-Wformat=]
    for(int i=1;i<=m;i++)scanf("%lld",&b[i]);
    ^
    foo.cpp:19:45: warning: too many arguments for format [-Wformat-extra-args]
    foo.cpp:11:13: warning: unused variable 'm' [-Wunused-variable]
    int n,t,m;
    ^
    测试数据 #0: Accepted, time = 6 ms, mem = 532 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 532 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 532 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 540 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 532 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 532 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 532 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 532 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 536 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 536 KiB, score = 10
    Accepted, time = 111 ms, mem = 540 KiB, score = 100
    代码
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    long long a[510],b[510];
    int f[510];
    int main()
    {
    int n,t,m;
    scanf("%d",&t);
    for(;t--;){
    int m,ans=0;
    memset(f,0,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%lld",&b[i]);
    for(int i=1;i<=n;i++){
    int maxn=0;
    for(int j=1;j<=m;j++)
    {
    if(b[j]<a[i])maxn=max(maxn,f[j]);
    if(b[j]==a[i])f[j]=maxn+1;
    ans=max(f[j],ans);
    }
    }
    printf("%d\n",ans);
    }
    return 0;
    }

  • 0
    @ 2020-05-15 21:45:09
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int M=505;
    int n,la,lb,a[M],b[M],ans=0;
    int f[M];
    void dp(){
        int mx=0;
        for(int i=1;i<=la;i++){
            mx=0;
            for(int j=1;j<=lb;j++){
                if(a[i]>b[j]) mx=max(mx,f[j]);
                if(a[i]==b[j]) f[j]=mx+1;
            }
        }
    }
    int main(int argc, const char * argv[]) {
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            memset(f,0,sizeof(f));ans=0;
            scanf("%d",&la);
            for(int i=1;i<=la;i++) scanf("%d",&a[i]);
            scanf("%d",&lb);
            for(int i=1;i<=lb;i++) scanf("%d",&b[i]);
            dp();
            for(int i=1;i<=lb;i++) ans=max(ans,f[i]);
            printf("%d\n",ans);
        }
        return 0;
    }
    
    
  • 0
    @ 2018-04-18 13:37:33

    #include<cstdio>
    #include<cstring>
    #define q 250
    #define w 2222
    using namespace std;
    typedef long long ll;
    int main() {

    ll n,f[q]={0},a1,b1,a[w],b[w],maxn;
    int m1,m2;
    cin>>n;
    for(int i=1; i<=n; i++)
    {

    cin>>m1;

    for(int i=1; i<=m1; i++)
    {
    cin>>a[i];
    }

    cin>>m2;

    for(int i=1; i<=m2; i++)
    {
    cin>>b[i];
    }

    for( int i = 1 ; i <= m1 ; i++ )
    {
    maxn = 0;
    for( int j = 1 ; j <= m2 ; j++ )
    if ( b[ j ] < a[ i ] )
    maxn = max( maxn , f[ j ] );
    else
    if ( b[ j ] == a[ i ] )
    f[ j ] = max( f[ j ] , maxn + 1 );
    }
    maxn = 0;
    for( int i = 1 ; i <= max(m1,m2) ; i++ )
    maxn = max( maxn , f[ i ] );
    cout<<maxn;
    }
    return 0;

    }

  • 0
    @ 2016-08-12 21:23:34

    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=500+10;
    int dp[maxn],inp[2][maxn];
    int len1,len2;
    int main()
    {
    int i,j,k,maxj,ans;
    cin>>k;
    while(k--)
    {
    cin>>len1;for(i=1;i<=len1;i++){cin>>inp[0][i];}
    cin>>len2;for(i=1;i<=len2;i++){cin>>inp[1][i];}
    memset(dp,0,sizeof(dp));
    for(i=1;i<=len1;i++)
    {
    maxj=0;
    for(j=1;j<=len2;j++)
    {
    if(inp[0][i]>inp[1][j]&&maxj<dp[j]){maxj=dp[j];}//protect the maxj;
    if(inp[0][i]==inp[1][j]){dp[j]=maxj+1;}
    }
    }
    ans=0;
    for(i=1;i<=len2;i++){ans=max(ans,dp[i]);}
    cout<<ans<<endl;
    }
    return 0;
    }

  • 0
    @ 2014-10-23 20:08:19

    我完了!
    这题难道不是LCS的LIS吗?哪里错了?
    ####代码:
    program incantation;
    type arr=array[1..500] of longint;
    var
    a,b,c:arr;
    f,flag:array[0..500,0..500] of integer;
    n,m1,m2,i,j,k,s:integer;
    procedure lis(x:arr;var n:integer);
    var
    z:array[1..500] of integer;
    i,j,max:integer;
    begin
    for i:=1 to n do z[i]:=1;
    for i:=n-1 downto 1 do
    begin
    max:=z[i];
    for j:=i to n do
    if (x[i]<x[j]) and (z[j]+1>max) then max:=z[j]+1;
    z[i]:=max;
    end;
    max:=0;
    for i:=1 to n do if max<z[i] then max:=z[i];
    n:=max;
    end;
    procedure lcs(x,y:integer);
    var
    i,j:integer;
    begin
    i:=x;j:=y;
    repeat
    case flag[i,j] of
    1:begin s:=s-1;c[s]:=a[i];i:=i-1;j:=j-1;end;
    2:i:=i-1;
    3:j:=j-1;
    end;
    until flag[i,j]=0;
    end;
    begin
    readln(n);
    for k:=1 to n do
    begin
    fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);
    fillchar(flag,sizeof(flag),0);
    read(m1);for i:=1 to m1 do begin read(a[i]);f[i,0]:=0;end;
    read(m2);for i:=1 to m2 do begin read(b[i]);f[0,j]:=0;end;
    for i:=1 to m1 do
    for j:=1 to m2 do
    if a[i]=b[j] then
    begin f[i,j]:=f[i-1,j-1]+1;flag[i,j]:=1;end
    else
    if f[i-1,j]>f[i,j-1] then
    begin f[i,j]:=f[i-1,j];flag[i,j]:=2;end
    else begin f[i,j]:=f[i,j-1];flag[i,j]:=3;end;
    s:=f[m1,m2]+1;
    lcs(m1,m2);
    s:=f[m1,m2];
    lis(c,s);
    writeln(s);
    end;
    readln;readln;
    end.

    • @ 2016-01-26 19:50:55

      这是LCIS,不同的

  • 0
    @ 2014-10-04 18:07:13

    。。

  • 0
    @ 2014-08-15 01:13:56

    fillchar(f,sizeof(f),0);
    read(a[0]);for i:=1 to a[0] do read(a[i]);
    read(b[0]);for i:=1 to b[0] do read(b[i]);
    for i:=1 to a[0] do
    begin
    max:=0;
    for j:=1 to b[0] do
    begin
    if (max<f[j]) and (a[i]>b[j]) then max:=f[j];
    if a[i]=b[j] then f[j]:=max+1;
    end;
    end;
    max:=-1000;
    for i:=1 to b[0] do if max<f[i] then max:=f[i];
    writeln(max);

  • 0
    @ 2014-08-15 00:05:27

    单调队列

  • 0
    @ 2014-03-27 11:38:34

    O(nm)算法,水过
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 444 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 444 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 448 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 448 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 448 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 440 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 448 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 440 KiB, score = 10
    测试数据 #8: Accepted, time = 0 ms, mem = 448 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 448 KiB, score = 10
    Accepted, time = 30 ms, mem = 448 KiB, score = 100

  • 0
    @ 2014-01-01 12:00:52

    Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
    有疑问请留言 共同进步

  • 0
    @ 2013-11-03 09:09:34

    var Max,i,j,k,l,m,n,AA,BB:Longint;
    F:array[0..500] of Longint;
    A,B:array[0..500] of Longint;

    Function MAxx(a,b:Longint):Longint;
    Begin
    If a>b then Exit(A) else Exit(B);
    ENd;

    Begin
    Readln(N);
    For i:=1 to N do
    Begin
    Fillchar(F,sizeof(F),0);
    Read(AA);For j:=1 to AA do Read(A[j]);
    Read(BB);For j:=1 to BB do Read(B[j]);
    For j:=1 to AA do
    Begin
    Max:=0;
    For k:=1 to BB do
    If B[k]<A[j] then Max:=Maxx(Max,F[k])
    Else If B[k]=A[j] then F[k]:=Maxx(F[k],Max+1);
    ENd;
    Max:=0;
    For j:=1 to BB do Max:=Maxx(Max,F[j]);
    Writeln(Max);
    End;
    ENd.

    • @ 2014-02-28 23:34:35

      大神可否讲解一下原理?

  • 0
    @ 2013-10-16 11:21:30

    var
    a,b,f:array[1..2000] of longint;
    i,j,n,max,k,q,w:longint;
    begin
    readln(n);
    for k:=1 to n do
    begin
    read(q);
    for i:=1 to q do
    read(a[i]);
    read(w);
    for j:=1 to w do
    read(b[j]);
    for i:=1 to q do
    begin
    max:=0;
    for j:=1 to w do
    begin
    if (a[i]>b[j])and(max<f[j]) then max:=f[j];
    if (a[i]=b[j])and(max+1>f[j]) then f[j]:=max+1;
    end;
    end;
    max:=0;
    for i:=1 to w do
    if f[i]>max then max:=f[i];
    writeln(max);
    fillchar(f,sizeof(f),0);
    end;
    end.

  • 0
    @ 2009-10-18 16:39:41

    好题!!!

    注意a,b是长整型

    有多组数据,忘了初值

    wa得不应该,该打,该打

  • 0
    @ 2009-10-11 14:52:25

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 41ms

    ├ 测试数据 08:答案正确... 400ms

    ├ 测试数据 09:答案正确... 588ms

    ├ 测试数据 10:答案正确... 400ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:1429ms

    唉 唉

  • 0
    @ 2010-03-30 17:04:33

    多年之后的今天,我终于想到了个O(N^2 (logN)^2)的算法...

    宋神牛比我早了近1年..

  • 0
    @ 2009-04-17 22:11:42

    自己发明了个最坏O(n^2*(logn)^2)的算法。

    注意是最坏情况下的,如果随即的话,平均O(c*n*(logn)^2)。

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 56ms

    ├ 测试数据 09:答案正确... 41ms

    ├ 测试数据 10:答案正确... 9ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:106ms

    改成基数排序后:

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 9ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:9ms

    • @ 2014-08-10 16:16:40

      请问是不是套两个树状?

  • 0
    @ 2008-11-13 13:49:47

    谁给一下题解,为什么我WA了这么多次

信息

ID
1264
难度
7
分类
动态规划 | LCS动态规划 | LIS 点击显示
标签
递交数
3412
已通过
626
通过率
18%
被复制
5
上传者