如何改进此算法以防止TLE是SPOJ提交？

Question

我试图解决以下问题:http: //www.spoj.pl/problems/TRIP/

我在C++中使用DP(动态编程)编写了一个解决方案(下面发布的代码).但我得到了TLE(时间限制超过).如何优化我的代码？

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;
string a,b;
vector<string> v;
int dp[85][85];

void filldp()
{
    for(int i = 0; i <= a.length(); i++)
        dp[i][0] = 0;
    for(int i = 0; i <= b.length(); i++)
        dp[0][i] = 0;   

    for(int i = 1; i <= a.length(); i++)
        for(int j = 1; j<= b.length(); j++)
        if(a[i-1] == b[j-1])
            dp[i][j] = dp[i-1][j-1] + 1;
        else
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 
}

vector<string> fillv(int i, int j)
{
    vector<string> returnset;
    if(i == 0 || j == 0)
    {   returnset.push_back("");
        return returnset;
    }

    if(a[i-1] == b[j-1])
        { 
          vector<string> set1 = fillv(i-1,j-1);
          for(int k = 0; k < set1.size(); k++)
          { 
            returnset.push_back(set1[k] + a[i-1]);
         }  
          return returnset;
        }

    else
        {
            if(dp[i][j-1] >= dp[i-1][j])
            {
                vector<string> set1 = fillv(i,j-1);
                returnset.insert(returnset.end(), set1.begin(), set1.end());
            }

            if(dp[i-1][j] >= dp[i][j-1])
            {
                vector<string> set2 = fillv(i-1,j);
                returnset.insert(returnset.end(), set2.begin(), set2.end());
            }

            return returnset;

        }       

}

void output()
{
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 0; i < v.size(); i++)
        cout << v[i] << endl;   
    cout << endl;       
}

int main()
{
    int T;
    cin >> T;

    while(T--)
    {
        memset(dp,-1,sizeof(dp));
        v.clear();
        cin >> a >> b;
        filldp();
        v = fillv(a.length(), b.length());
        output();
    }
    return 0;
}

我的猜测是,有很多传递数据结构可以避免,但我无法弄清楚如何.

Answer 1

你正在做的第一个错误的事情是使用cin和cout,这非常慢.切勿使用cin和cout进行比赛编程!我只是将cin/cout改为scanf/printf,从TLE转到AC.