Как я могу улучшить этот алгоритм, чтобы предотвратить отправку SPOJ?

Question

Я пытаюсь решить следующую проблему: http://www.spoj.pl/problems/TRIP/

Я написал решение с использованием DP (динамическое программирование) на C ++ (код приведен ниже). Но я получаю 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

Вы можете значительно сократить время выполнения, взяв ввод с помощью 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 таково, что весь ввод может быть приняттолько в несколько «круговых поездок» (в данном случае, в идеале, один).Настройте его по мере необходимости.Эта техника очень эффективна в соревнованиях по программированию, чтобы получить преимущество над оппонентом по времени выполнения.

Надеюсь, это поможет!

Answer 3

когда вы знаете максимальный размер числа ответов, лучше использовать массив вместо вектора, потому что он намного быстрее, чем вектор.(«Существует по крайней мере одна такая поездка, но никогда не бывает более 1000 разных»)

function fillv тратит много времени в коде.потому что он получает много места во время выполнения и освобождает его (из-за локального пространства для функции fillv).для этого лучше использовать глобальный ответ.

для ввода и вывода для завершения ответа «Гэндальфа Серого», если вы хотите использовать cin и cout, лучше использовать std::ios::sync_with_stdio(false); (для ускоренияваш io runtime) однако printf и scanf намного быстрее, чем этот.