Wie kann ich diesen Algorithmus verbessern, um zu verhindern, dass TLE SPOJ-Submission ist?

Question

Ich versuche, das folgende Problem zu lösen: http://www.spoj.pl/problems/TRIP/

ich eine Lösung mit DP (Dynamic Programming) in C++ geschrieben (Code unten geschrieben). Aber ich bekomme TLE (Time Limit Exceeded). Wie kann ich meinen Code optimieren?

#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; 
} 

Meine Vermutung ist hier, dass es viel um Datenstrukturen vorbei, die vermieden werden können, aber ich kann nicht genau herausfinden, wie.

Answer 1

Die erste falsche Sache, die Sie tun, ist mit Cin und Cout, die schrecklich langsam sind. Benutze nie cin und cout für die Contest Programmierung! Ich bin von TLE nach AC gewechselt, indem ich cin/cout in scanf/printf geändert habe.

Answer 2

Wenn Sie die maximale Größe der Anzahl der Antworten wissen, ist es besser, Array anstelle von Vektor zu verwenden, weil es viel schneller als Vektor ist. ("Es gibt mindestens eine solche Fahrt, aber nie mehr als 1000 verschiedene")

Funktion fillv verschwendet viel Zeit im Code. weil es in Runtime viel Platz bekommt und es freigibt (wegen lokalem Platz für fillv Funktion). Es ist besser, globale Antworten dafür zu verwenden.

für die Eingabe und Ausgabe, um die Antwort von "Gandalf the Gray" zu vervollständigen, wenn Sie cin und cout verwenden möchten, ist es besser, std::ios::sync_with_stdio(false); zu verwenden (um Ihre io Laufzeit zu beschleunigen), aber printf und scanf ist viel schneller als das .

Answer 3

Sie können die Ausführungszeit stark reduzieren, indem Sie Eingaben mit fread() oder fread_unlocked() vornehmen (wenn Ihr Programm single-threaded ist). Das einmalige Sperren/Entsperren des Eingabestreams dauert nur eine vernachlässigbare Zeit, ignorieren Sie das also. Hier

ist der Code:

#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; 
} 

Das in C++ umgesetzt wird. In C müssen Sie iostream nicht einfügen, Funktion isdigit() ist implizit verfügbar.

Sie können Eingabe als ein Strom von Zeichen nehmen, indem Sie getc1() aufrufen und Ganzzahleingabe durch Aufrufen von input() nehmen.

Die ganze Idee hinter der Verwendung von fread() ist, große Blöcke von Eingabe auf einmal zu nehmen. Der Aufruf von scanf()/printf() nimmt beim Sperren und Entsperren von Streams immer wieder wertvolle Zeit in Anspruch, was in einem Single-Thread-Programm völlig überflüssig ist.

Stellen Sie außerdem sicher, dass der Wert maxio so ist, dass alle Eingaben nur in ein paar "Roundtrips" erfolgen können (idealerweise in einem Fall). Tweak es wie nötig. Diese Technik ist sehr effektiv in Programmierwettbewerben, um einen Vorteil gegenüber dem Gegner in Bezug auf die Ausführungszeit zu erzielen.

Hoffe, das hilft!