Làm cách nào để cải thiện thuật toán này để ngăn chặn TLE là gửi SPOJ?

Question

Tôi đang cố gắng giải quyết vấn đề sau: http://www.spoj.pl/problems/TRIP/

Tôi đã viết giải pháp sử dụng DP (Lập trình động) trong C++ (mã được đăng bên dưới). Nhưng tôi nhận được TLE (Time Limit Exceeded). Làm cách nào để tối ưu hóa mã của tôi?

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

Tôi đoán ở đây là có rất nhiều chuyển đổi cấu trúc dữ liệu có thể tránh được nhưng tôi không thể tìm ra cách chính xác.

Answer 1

Điều sai lầm đầu tiên bạn đang thực hiện là sử dụng cin và cout, điều này cực kỳ chậm. Không bao giờ sử dụng cin và cout để lập trình cuộc thi! Tôi đã đi từ TLE để AC chỉ bằng cách thay đổi cin/cout để scanf/printf.

Answer 2

khi bạn biết kích thước tối đa của số câu trả lời tốt hơn nên sử dụng mảng thay vì véc tơ vì nó nhanh hơn rất nhiều so với vectơ. ("Có ít nhất một chuyến đi như vậy, nhưng không bao giờ có hơn 1000 chuyến đi khác nhau")

chức năng fillv phí rất nhiều thời gian trong mã. bởi vì nó nhận được rất nhiều không gian trong thời gian chạy và giải phóng nó (vì không gian địa phương cho hàm fillv). tốt hơn là sử dụng câu trả lời toàn cầu cho điều đó.

cho đầu vào và đầu ra để hoàn thành câu trả lời "Gandalf the Grey", nếu bạn thích sử dụng cin và cout, tốt hơn nên sử dụng std::ios::sync_with_stdio(false); (để tăng tốc độ thời gian chạy io), tuy nhiên printf và scanf nhanh hơn nhiều so với .

Answer 3

Bạn có thể giảm đáng kể thời gian thực hiện bằng cách lấy đầu vào bằng cách sử dụng fread() hoặc fread_unlocked() (nếu chương trình của bạn là đơn luồng). Khóa/Mở khóa luồng đầu vào chỉ một lần mất thời gian không đáng kể, vì vậy hãy bỏ qua điều đó.

Đây là mã:

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

này được thực hiện trong C++. Trong C, bạn sẽ không cần phải bao gồm iostream, chức năng isdigit() hoàn toàn khả dụng.

Bạn có thể nhập đầu vào dưới dạng luồng ký tự bằng cách gọi getc1() và nhập số nguyên bằng cách gọi input().

Toàn bộ ý tưởng đằng sau việc sử dụng fread() là lấy khối lượng lớn dữ liệu đầu vào cùng một lúc. Gọi số scanf()/printf(), liên tục mất thời gian quý báu khi khóa và mở khóa các luồng hoàn toàn dư thừa trong chương trình một luồng đơn.

Cũng đảm bảo rằng giá trị của maxio là sao cho tất cả đầu vào có thể được thực hiện trong một vài "khứ hồi" chỉ (lý tưởng nhất, trong trường hợp này). Tinh chỉnh nó khi cần thiết. Kỹ thuật này có hiệu quả cao trong các cuộc thi lập trình, để đạt được lợi thế hơn đối thủ của bạn về thời gian thực hiện.

Hy vọng điều này sẽ hữu ích!