Paste will expire never.
- // Очно-заочный кружок
- // Занятие №8. Учебные задачи
- // Задача B. Наибольшая общая подпоследовательность с восстановлением ответа
- // ibelyaev: 24Oct2011
- // http://cppalgo.blogspot.com/2011/04/blog-post.htm
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <string>
- #include <string.h>
- #include <cmath>
- #include <queue>
- #include <vector>
- #include <map>
- #include <stdlib.h> // for exit(0)
- #include <stack>
- #include <list>
- #include <ctime>
- #include <set>
- using namespace std;
- const int EMPTY = -1;
- int n,m;
- vector<int> A,B,res;
- vector<vector<int> > mem;
- void input(vector<int> &mas, int &size) {
- scanf("%d",&size);
- mas.resize(size+1);
- for (int i=1;i<=size;++i)
- scanf("%d", &mas[i]);
- }
- void input(){
- input(A,n);
- input(B,m);
- mem.resize(n+1,vector<int>(m+1,EMPTY));
- }
- int LCS(int a, int b) {
- if (!a || !b ) return 0;
- if (mem[a][b] != EMPTY)
- return mem[a][b];
- int res;
- if (A[a] == B[b])
- res = LCS(a-1,b-1) + 1;
- else
- res = max(LCS(a-1,b),LCS(a,b-1));
- return mem[a][b] = res;
- }
- void solve(){
- int size = LCS(n, m);
- int a = n, b = m;
- res.resize(size);
- int pos = size - 1;
- while (a && b ) {
- if (A[a] == B[b]) {
- res[pos--] = A[a];
- a--; b--;
- }
- else {
- if (mem[a-1][b] > mem[a][b-1])
- a--;
- else
- b--;
- }
- }
- }
- void output() {
- for (int i=0;i<res.size();++i)
- printf("%d ", res[i]);
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- output();
- return 0;
- }
Editing is locked.