document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. /*
  2.  * User: asm149
  3.  * Problem code: CRSCNTRY
  4.  * Algo: DP - Longest Common Subsequence
  5. */
  6.  
  7. #include <cstdio>
  8.  
  9. inline int read ()
  10. {
  11.     char c;
  12.     int n = 0;
  13.  
  14.     while ((c = getchar_unlocked ()) < 48);
  15.     n += (c - \'0\');
  16.    
  17.     while ((c = getchar_unlocked ()) >= 48)
  18.       n = n * 10 + (c - \'0\');
  19.    
  20.     return n;
  21. }
  22.  
  23. int max (int a, int b) { return a > b ? a : b; }
  24.  
  25. int getLCSLength (int agnes[], int a, int tom[], int t)
  26. {
  27.     int LCS[a+1][t+1];
  28.     for (int i = 0; i <= a; i++)
  29.         LCS[i][0] = 0;
  30.     for (int i = 0; i <= t; i++)
  31.         LCS[0][i] = 0;
  32.     for (int i = 1; i <= a; i++)
  33.     {
  34.         for (int j = 1; j <= t; j++)
  35.         {
  36.             if (agnes[i-1] == tom[j-1])
  37.                 LCS[i][j] = LCS[i-1][j-1] + 1;
  38.             else
  39.                 LCS[i][j] = max (LCS[i-1][j], LCS[i][j-1]);
  40.         }
  41.     }
  42.     return LCS[a][t];
  43. }
  44.  
  45. int main (void)
  46. {
  47.     int d = read ();
  48.     while (d--)
  49.     {
  50.         int agnes[2001], m = 0;
  51.         int temp = 1, a = 0;
  52.         while (temp)
  53.         {
  54.             temp = read ();
  55.             agnes[a++] = temp;
  56.         }
  57.         while (true)
  58.         {
  59.             int tom[2001], t = 1;
  60.             temp = read ();
  61.             if (temp == 0)
  62.                 break;
  63.             tom[0] = temp;
  64.             temp = 1;
  65.             while (temp)
  66.             {
  67.                 temp = read ();
  68.                 tom[t++] = temp;
  69.             }          
  70.             m = max (m, getLCSLength (agnes, a-1, tom, t-1));
  71.         }
  72.         printf ("%d\\n", m);
  73.     }
  74.     return 0;
  75. }
');