Tôi đang cố gắng giải quyết vấn đề sau: http://www.spoj.pl/problems/TRIP/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?
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.
TLE là gì? Ba chữ Evasiveness? Bạn sẽ nhận được nhiều câu trả lời tốt hơn nếu bạn không yêu cầu người trả lời quen thuộc với thuật ngữ của một nền văn hóa phụ cụ thể. – RBarryYoung