v 0. Pasted by slipstak2 as cpp at 2011-10-24 21:03:55 MSK and set expiration to never.

Paste will expire never.

  1. // Очно-заочный кружок
  2. // Занятие №8. Учебные задачи
  3. // Задача B. Наибольшая общая подпоследовательность с восстановлением ответа
  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. const int EMPTY = -1;
  25. int n,m;
  26. vector<int> A,B,res;
  27. vector<vector<int> > mem;
  28. void input(vector<int> &mas, int &size) {
  29.     scanf("%d",&size);
  30.     mas.resize(size+1);
  31.     for (int i=1;i<=size;++i)
  32.         scanf("%d", &mas[i]);
  33. }
  34. void input(){
  35.     input(A,n);
  36.     input(B,m);
  37.     mem.resize(n+1,vector<int>(m+1,EMPTY));
  38. }
  39. int LCS(int a, int b) {
  40.     if (!a || !b ) return 0;
  41.     if (mem[a][b] != EMPTY)
  42.         return mem[a][b];
  43.     int res;
  44.     if (A[a] == B[b])
  45.         res = LCS(a-1,b-1) + 1;
  46.     else
  47.         res = max(LCS(a-1,b),LCS(a,b-1));
  48.     return mem[a][b] = res;
  49. }
  50. void solve(){
  51.     int size = LCS(n, m);
  52.     int a = n, b = m;
  53.     res.resize(size);
  54.     int pos = size - 1;
  55.     while (a  && b ) {
  56.         if (A[a] == B[b]) {
  57.             res[pos--] = A[a];
  58.             a--; b--;
  59.         }
  60.         else {
  61.             if (mem[a-1][b] > mem[a][b-1])
  62.                 a--;
  63.             else
  64.                 b--;
  65.         }
  66.     }
  67. }
  68. void output() {
  69.     for (int i=0;i<res.size();++i)
  70.         printf("%d ", res[i]);
  71. }
  72. int main()
  73. {
  74.     freopen("input.txt","r",stdin);
  75.     freopen("output.txt","w",stdout);
  76.  
  77.     input();
  78.     solve();
  79.     output();
  80.  
  81.     return 0;
  82. }


Editing is locked.