fork(1) download
  1. #include <algorithm>
  2. #include <numeric>
  3. #include <utility>
  4. #include <functional>
  5. #include <bitset>
  6. using namespace std;
  7. //
  8. #define lp(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
  9. #define MAX 109
  10. #define dex [i][j]
  11. int DP[MAX][MAX];
  12. int ST[MAX][MAX] = {0};
  13. //
  14. int mark = 0;
  15. int n, m;
  16. int *s1, *s2;
  17. //
  18. int doit(int i = 0, int j = 0)
  19. {
  20. if(i == n || j == m)
  21. return 0;
  22.  
  23. if(ST dex == mark)
  24. return DP dex;
  25. ST dex = mark;
  26.  
  27. if(s1[i] == s2[j])
  28. return DP dex = 1 + doit(i+1, j+1);
  29.  
  30. int c1 = doit(i+1, j);
  31. int c2 = doit(i, j+1);
  32. return DP dex = max(c1, c2);
  33. }
  34. //
  35. int main()
  36. {
  37. while( scanf("%d %d", &n, &m) && !(n == 0 && m == 0) )
  38. {
  39. s1 = new int[n];
  40. s2 = new int[m];
  41. lp(i, n)
  42. scanf("%d", &s1[i]);
  43. lp(i, m)
  44. scanf("%d", &s2[i]);
  45. printf("Twin Towers #%d\nNumber of Tiles : %d\n\n", ++mark, doit());
  46. }
  47. }
Success #stdin #stdout 0s 3568KB
stdin
7 6
20 15 10 15 25 20 15
15 25 10 20 15 20
8 9
10 20 20 10 20 10 20 10
20 10 20 10 10 20 10 10 20
0 0
 
stdout
Twin Towers #1
Number of Tiles : 0

Twin Towers #2
Number of Tiles : 6