首页 > 代码库 > HDU 1423

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\n",lics);35         if(t)printf("\n");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\n",lics);36         if(t)printf("\n");37     }38 }

 

HDU 1423