HDU 1423

lics水题一维数组记录

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string.h>
 4 using namespace std;
 5 const int N=502;
 6 int a[N],b[N];
 7 int f[N];
 8 int n,m,lics;
 9 void LICS(){
10     memset(f,0,sizeof(f));
11     lics=0;
12     for(int i=1;i<=n;i++){
13         int max=0;
14         for(int j=1;j<=m;j++){
15             if(a[i]>b[j]&&max<f[j])max=f[j];
16             if(a[i]==b[j])f[j]=max+1;
17         }
18     }
19     for(int i=1;i<=m;i++)if(lics<f[i])lics=f[i];
20 }
21 int main(){
22     int t;
23     scanf("%d",&t);
24     while(t--){
25         scanf("%d",&n);
26         for(int i=1;i<=n;i++){
27             scanf("%d",&a[i]);
28         }
29         scanf("%d",&m);
30         for(int i=1;i<=m;i++){
31             scanf("%d",&b[i]);
32         }
33         LICS();
34         printf("%d
",lics);
35         if(t)printf("
");
36     }
37 }

二位数组记录

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string.h>
 4 using namespace std;
 5 const int N=502;
 6 int a[N],b[N];
 7 int f[N][N];
 8 int n,m,lics;
 9 void LICS(){
10     memset(f,0,sizeof(f));
11     lics=0;
12     for(int i=1;i<=n;i++){
13         int max=0;
14         for(int j=1;j<=m;j++){
15             f[i][j]=f[i-1][j];
16             if(a[i]>b[j]&&max<f[i-1][j])max=f[i-1][j];
17             if(a[i]==b[j])f[i][j]=max+1;
18         }
19     }
20     for(int i=1;i<=m;i++)if(lics<f[n][i])lics=f[n][i];
21 }
22 int main(){
23     int t;
24     scanf("%d",&t);
25     while(t--){
26         scanf("%d",&n);
27         for(int i=1;i<=n;i++){
28             scanf("%d",&a[i]);
29         }
30         scanf("%d",&m);
31         for(int i=1;i<=m;i++){
32             scanf("%d",&b[i]);
33         }
34         LICS();
35         printf("%d
",lics);
36         if(t)printf("
");
37     }
38 }