首页 > 代码库 > CSU 1120 病毒

CSU 1120 病毒

最长公共上升子序列(LCIS)

裸的算法题,没什么好说的。

 

ps:找这个算法的时候看到某队省赛的时候不会,同病相怜哈,还好我们只是训练赛不会。灭哈哈哈~

 

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5  6         int f[1005][1005]; 7 int main (){//cout<<"error"<<endl; 8         int n1,n2; 9         int a[1005],b[1005];10         int max;11     int t;12     cin>>t;13     while (t--){14         cin>>n1;15         for (int i=1;i<=n1;i++)16             cin>>a[i];17         cin>>n2;18         for (int i=1;i<=n2;i++)19             cin>>b[i];20         memset (f,0,sizeof f);21         for (int i=1;i<=n1;i++){22             max=0;23             for (int j=1;j<=n2;j++){24                 f[i][j]=f[i-1][j];25                 if (a[i]>b[j]&&f[i-1][j]>max)26                     max=f[i-1][j];27                 if (a[i]==b[j])28                     f[i][j]=max+1;29             }30         }31         int ans=0;32         for (int i=1;i<=n2;i++)33             if (f[n1][i]>ans)34                 ans=f[n1][i];//cout<<ans<<" ";35         cout<<ans<<endl;36     }37     return 0;38 }

 

CSU 1120 病毒