Почему это решение DP дает TLE? - PullRequest
Новая
       26

Почему это решение DP дает TLE?

0 голосов
/ 13 октября 2019

Я решаю одну из прошлых проблем Google Kickstart 2019: «Уплощение»

Возможное решение DP описано в разделе «Анализ» на странице связанный , но моя реализация этого подхода получает TLE для набора тестов 2. Почему?

Вот что я сделал: 

    #include <iostream>
    #include <map>
    #include <cmath>
    #include <cstring>
    using namespace std;

    int heights[200];
    int T,N,K;
    int memo[200][200];

    int R(int I,int J){
       map<int,int> rates;
       int largest_group = -1;
       for(int i=I;i<=J;i++){
           if(rates.find(heights[i]) == rates.end()) rates[heights[i]] = 1;
           else rates[heights[i]] ++;
           if(rates[heights[i]] > largest_group) largest_group = rates[heights[i]];
       }
       return J-I+1 - largest_group;
    }

    int P(int Z,int K){

       if(Z<=0) return 0;
       if(K==0) return R(0,Z);

       if(memo[Z][K] != -1) return memo[Z][K];

       int res = 1000000;
       for(int i=0;i<=Z;i++)
          res = min( res, P(i-1,K-1)+R(i,Z) );

       return (memo[Z][K] = res);
    }
    int main(){
       cin>>T;
       int t = 0;
       while(++t <= T){
         memset(memo,-1,sizeof memo);
         cin>>N>>K; 
         for(int i=0;i<N;i++)
             cin>>heights[i];

         cout<<"Case #"<<t<<": "<<P(N-1,K)<<endl; 
       }
       return 0;
    }

1 Ответ

0 голосов
/ 13 октября 2019

Я не читал проблему, просто посмотрел ваш код.

В C ++ map является упорядоченным контейнером и имеет среднюю сложность O (log n) как для вставки, так и для доступа к элементу. Вы можете заменить его на unordered_map, который предлагает те же операции в среднем постоянном времени.

Кроме того, поскольку доступ к несуществующему ключу на карте (или неупорядоченной карте) фактически добавляет новый элемент с этим ключом (и вв этом случае с нулевым значением по умолчанию) вы можете переписать инструкцию в цикле for внутри функции R () следующим образом:

largest_group = max(largest_group, ++rates[heights[i]]);

...