#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;
}

/*

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;
}

#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;
}

#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;
}

#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;

}

#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;
}

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;
}

我完了！
这题难道不是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.

。。

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);

单调队列

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

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

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.

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.

好题！！！

注意a，b是长整型

有多组数据，忘了初值

wa得不应该，该打，该打

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

唉 唉

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

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

自己发明了个最坏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

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