v 0. Pasted by slipstak2 as cpp at 2011-10-24 20:57:29 MSK and set expiration to never.

Paste will expire never.

  1. // Очно-заочный кружок
  2. // Занятие №8. Учебные задачи
  3. // Задача A. Наибольшая общая подпоследовательность
  4. // ibelyaev: 24Oct2011
  5. // http://cppalgo.blogspot.com/2011/04/blog-post.htm
  6.  
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <algorithm>
  10. #include <string>
  11. #include <string.h>
  12. #include <cmath>
  13. #include <queue>
  14. #include <vector>
  15. #include <map>
  16. #include <stdlib.h> // for exit(0)
  17. #include <stack>
  18. #include <list>
  19. #include <ctime>
  20. #include <set>
  21.  
  22. using namespace std;
  23.  
  24. int n,m;
  25. vector<int> A,B;
  26. vector<vector<int> > mem;
  27. void input(vector<int> &mas, int &size) {
  28.     scanf("%d",&size);
  29.     mas.resize(size);
  30.     for (int i=0;i<size;++i)
  31.         scanf("%d", &mas[i]);
  32. }
  33. void input(){
  34.     input(A,n);
  35.     input(B,m);
  36.     mem.resize(n,vector<int>(m,-1));
  37. }
  38. int LCS(int a, int b) {
  39.     if (a < 0 || b < 0) return 0;
  40.     if (mem[a][b] != -1)
  41.         return mem[a][b];
  42.     int res;
  43.     if (A[a] == B[b])
  44.         res = LCS(a-1,b-1) + 1;
  45.     else
  46.         res = max(LCS(a-1,b),LCS(a,b-1));
  47.     return mem[a][b] = res;
  48. }
  49. void solve(){
  50.     printf("%d", LCS(n-1, m-1));
  51. }
  52. int main()
  53. {
  54.     freopen("input.txt","r",stdin);
  55.     freopen("output.txt","w",stdout);
  56.  
  57.     input();
  58.     solve();
  59.  
  60.     return 0;
  61. }


Editing is locked.