fork download
copy 
  1. //https://c...content-available-to-author-only...s.fi/problemset/task/3403
  2. /*
  3. dp[i][j] dãy cong tăng dài nhất khi xét đến phần tử thứ i của dãy 1 và phần tử thứ j của dãy 2
  4. */
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7.  
  8. const long long MaxN = 1005;
  9.  
  10. long long n,m;
  11. long long a[MaxN],b[MaxN];
  12. long long dp[MaxN][MaxN];
  13. vector<long long> res;
  14.  
  15. void input()
  16. {
  17.     cin >> n >> m;
  18.     for(long long i=1;i<=n;i++) cin >> a[i];
  19.     for(long long i=1;i<=m;i++) cin >> b[i];
  20. }
  21.  
  22. void solve()
  23. {
  24.     for(long long i=1;i<=n;i++)
  25.     {
  26.         for(long long j=1;j<=m;j++)
  27.         {
  28.             if(a[i]==b[j])
  29.                 dp[i][j]=dp[i-1][j-1]+1;
  30.             else
  31.                 dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  32.         }
  33.     }
  34.  
  35.     cout << dp[n][m] << '\n';
  36.  
  37.     long long i=n,j=m;
  38.  
  39.     while(i>0&&j>0)
  40.     {
  41.         if(a[i]==b[j])
  42.         {
  43.             res.push_back(a[i]);
  44.             i--;
  45.             j--;
  46.         }
  47.         else
  48.         {
  49.             if(dp[i-1][j]>=dp[i][j-1])
  50.                 i--;
  51.             else
  52.                 j--;
  53.         }
  54.     }
  55.  
  56.     reverse(res.begin(),res.end());
  57.  
  58.     for(long long x:res)
  59.         cout << x << ' ';
  60. }
  61.  
  62. int main()
  63. {
  64.     ios_base::sync_with_stdio(0);
  65.     cin.tie(0);
  66.  
  67.     input();
  68.     solve();
  69. }
  70.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/GwQiRu
language:
C++14 (gcc 8.3)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!