[POJ 1934] Trip

[题目链接]

http://poj.org/problem?id=1934

[算法]

先用dp求出LCS，然后搜索即可，注意加上一些剪枝

[代码]

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXLEN 85

int i,j,la,lb,len,l;

string a,b;

int f[MAXLEN][MAXLEN],pa[MAXLEN][MAXLEN],pb[MAXLEN][MAXLEN];

string q[];

inline void dfs(int dep,int pos1,int pos2,string t)

{

        int i;

        if (dep > len) q[++l] = t;

        if (pos1 <  || pos2 < ) return;

        if (f[pos1][pos2] != len - dep + ) return;

        if (dep + pos1 < len || dep + pos2 < len) return;

        if (l >= ) return;

        for (i = ; i < ; i++)

        {

                if (l >= ) return;

                if (pa[i][pos1] != - && pb[i][pos2] != -)

                        dfs(dep + ,pa[i][pos1] - ,pb[i][pos2] - ,(char)(i + 'a') + t);

        }

}

int main()

{

        cin.tie();

        ios :: sync_with_stdio();

        while (cin >> a)

        {

                cin >> b;

                la = a.size();

                lb = b.size();

                for (i = ; i < la; i++)

                {

                        for (j = ; j < lb; j++)

                        {

                                f[i][j] = ;

                        }

                }

                for (i = ; i < la; i++)

                {

                        for (j = ; j < lb; j++)

                        {

                                if (a[i] == b[j])

                                {

                                        if (i >=  && j >= ) f[i][j] = f[i - ][j - ] + ;

                                        else f[i][j] = (a[i] == b[j]);

                                }

                                if (i >= ) f[i][j] = max(f[i][j],f[i - ][j]);

                                if (j >= ) f[i][j] = max(f[i][j],f[i][j - ]);

                        }

                }

                for (i = ; i < ; i++)

                {

                        for (j = ; j < la; j++)

                        {

                                pa[i][j] = -;

                        }

                }

                for (i = ; i < ; i++)

                {

                        for (j = ; j < la; j++)

                        {

                                if (a[j] == 'a' + i) pa[i][j] = j;

                                else if (j > ) pa[i][j] = pa[i][j - ];

                        }

                }

                for (i = ; i < ; i++)

                {

                        for (j = ; j < lb; j++)

                        {

                                pb[i][j] = -;

                        }

                }

                for (i = ; i < ; i++)

                {

                        for (j = ; j < lb; j++)

                        {

                                if (b[j] == 'a' + i) pb[i][j] = j;

                                else if (j > ) pb[i][j] = pb[i][j - ];

                        }

                }

                len = f[la - ][lb - ];

                l = ;

                dfs(,la - ,lb - ,"");

                sort(q+,q+l+);

                for (i = ; i <= l; i++) cout<< q[i] << endl;

        }

        return ;

}