如何改进此算法以防止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进行比赛编程！我已经从TLE变成了AC，只需将cin/cout改为scanf/printf即可。

Answer 2

当你知道答案数量的最大值时，最好使用数组而不是向量 ，因为它比向量快很多。 （“至少有一次这样的行程，但从未超过1000个不同的行程”）

功能fillv浪费了大量的时间在代码中。因为它在运行时获得大量空间并释放它（因为fillv函数的本地空间）。为此，最好使用全局答案。

用于输入和输出以完成“Gandalf the Gray”的回答，如果您喜欢使用cin和cout，最好使用std::ios::sync_with_stdio(false);（以加速您的io运行时），但是printf和scanf比这更快。

Answer 3

通过使用fread()或fread_unlocked()（如果程序是单线程）输入输入，可以大大缩短执行时间。锁定/解锁输入流只需要一次，可以忽略不计。

下面是代码：

#include <iostream> 

int maxio=1000000; 
char buf[maxio], *s = buf + maxio; 

inline char getc1(void) 
{ 
    if(s >= buf + maxio) { fread_unlocked(buf,sizeof(char),maxio,stdin); s = buf; } 
    return *(s++); 
} 
inline int input() 
{ 
    char t = getc1(); 
    int n=1,res=0; 
    while(t!='-' && !isdigit(t)) t=getc1(); if(t=='-') 
    { 
     n=-1; t=getc1(); 
    } 
    while(isdigit(t)) 
    { 
    res = 10*res + (t&15); 
    t=getc1(); 
    } 
    return res*n; 
} 

这在C++实现。在C中，您不需要包含iostream，函数isdigit()是隐含可用的。

您可以通过调用getc1()作为字符流输入并通过调用input()来接受整数输入。

使用fread()后面的整个想法是一次接受大块输入。调用scanf()/printf()，反复占用锁定和解锁流的宝贵时间，这在单线程程序中是完全冗余的。

还要确保maxio的值是这样的，即所有输入只能在几个“往返”（最好是一个，在这种情况下）中进行。根据需要调整它。这种技术在编程比赛中非常有效，可以在执行时间方面获得胜过对手的优势。

希望这会有所帮助！