44 条题解
-
2Elucidator LV 7 @ 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;
} -
22015-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;
} -
12023-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; }
-
12015-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;
} -
02020-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; }
-
02018-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;}
-
02016-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;
} -
02014-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. -
02014-10-04 18:07:13@
。。
-
02014-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); -
02014-08-15 00:05:27@
单调队列
-
02014-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 -
02014-01-01 12:00:52@
Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步 -
02013-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. -
02013-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. -
02009-10-18 16:39:41@
好题!!!
注意a,b是长整型
有多组数据,忘了初值
wa得不应该,该打,该打 -
02009-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唉 唉
-
02010-03-30 17:04:33@
多年之后的今天,我终于想到了个O(N^2 (logN)^2)的算法...
宋神牛比我早了近1年.. -
02009-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 -
02008-11-13 13:49:47@
谁给一下题解,为什么我WA了这么多次