fork download 
  1. #include<bits/stdc++.h>
  2. #define MOD 1000000007
  3. #define pb push_back
  4. #define ll long long
  5. using namespace std;
  6.  
  7. int main()
  8. {
  9.     std::ios_base::sync_with_stdio(0);
  10.     int t;
  11.     cin >> t;
  12.     while (t--)
  13.     {
  14.         int n;
  15.         cin >> n;
  16.         vector<string> a(n);
  17.         for (int i=0; i<n; ++i) cin >> a[i];
  18.         int res=MOD;
  19.         for (int i=1; i<n; ++i)
  20.         {
  21.             int m=a[0].size();
  22.             int dp[m+1][a[i].size()+1];
  23.             for (int j=0; j<=m; ++j) dp[j][0]=0;
  24.             for (int j=0; j<=a[i].size(); ++j) dp[0][j]=0;
  25.             string tmp;
  26.             for (int j=1; j<=m; ++j)
  27.             {
  28.                 for (int k=1; k<=a[i].size(); ++k)
  29.                 {
  30.                     if (a[0][j-1]==a[i][k-1])
  31.                     {
  32.                         dp[j][k]=dp[j-1][k-1]+1;
  33.                         char c=a[0][j-1];
  34.                         tmp+=c;
  35.                     }
  36.                     else dp[j][k]=max(dp[j-1][k], dp[j][k-1]);
  37.                 }
  38.             }
  39.             if (dp[m][a[i].size()]<res) res=dp[m][a[i].size()];
  40.             a[0]=tmp;
  41.         }
  42.         cout << res << "\n";
  43.     }
  44. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
1
3
12345
45321
21543
stdout 
2
https://ideone.com/jH7wIe
language:
C++14 (gcc 8.3)
created:
19 days 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!