TLEがSPOJの提出を防ぐためにこのアルゴリズムを改善するにはどうすればよいですか？私は次のような問題を解決しようとしています

Question

： http://www.spoj.pl/problems/TRIP/

私はC++（コード下記掲載）でDPを用いて溶液（動的計画法）を書きました。しかし、私はTLE（Time Limit Exceeded）を取得します。コードを最適化するにはどうすればよいですか？ここ

#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を使用しないでください！私はscanf/printfにcin/coutを変更するだけで、TLEからACに移行しました。

Answer 2

答えの最大サイズを知っている場合は、ベクターよりも配列が速いので、ベクトル ではなく配列を使用するほうが良いです。 （「少なくとも1つの旅行がありますが、決して1000以上の異なるものはありません」

機能fillvはコード内で多くの時間を無駄にします。それは実行時に多くのスペースを得てフリーにするためです（fillvのローカルスペースのため）。それはグローバルな答えを使用する方が良いです。

"Gandalf the Grey"の答えを完成させるためには、cinとcoutを使いたい場合は、std::ios::sync_with_stdio(false);を使用する方が良いですが、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の値は、すべての入力を数回の「ラウンドトリップ」（理想的には1つ）で取ることができるようにしてください。必要に応じてそれを微調整します。このテクニックは、競技のプログラミングにおいて、実行時間の面で相手を圧倒するために非常に有効です。

希望すると便利です。