Медали

Ми паѓа на време со рекурзија на време О(2^N)
дајте идеја некоја

Има решение со сложеност O(N) и со O(N*lg(N)). О(N) решението е динамичко, моето е 2 димензионално, [N][3]. Другото е барање на најголема неопаѓачка подниза, што се прави во O(N*lg(N)) со бинарно пребарување. Ако добро памтам во двата случаи треба да почнеш и од напред и од назад. Ако не успееш, пиши пак, ќе објаснам подобро, не сакам сега затоа што може сакаш да се помачиш уште малце.

Не успеав да ја решам. Дај уште некој совет.

Ти пратив приватна порака.

hristijan wrote:Има решение со сложеност O(N) и со O(N*lg(N)). О(N) решението е динамичко, моето е 2 димензионално, [N][3]. Другото е барање на најголема неопаѓачка подниза, што се прави во O(N*lg(N)) со бинарно пребарување. Ако добро памтам во двата случаи треба да почнеш и од напред и од назад. Ако не успееш, пиши пак, ќе објаснам подобро, не сакам сега затоа што може сакаш да се помачиш уште малце.

Те молам ако не ти е тешко да ми ги објасниш двата начина! Затоа што и мене ми текна да ја решавам со динамичко, ама на 7 тест примери ми паѓа на време. Веројатно затоа што јас имам два вгнездени циклуса, а се работи за големи вредности (до 30000).

Еве го моето решение со динамичко.. Иначе ако може објаснување (или некој линк со објаснување

) за алгоритмот за наоѓање на најдолга неопаѓачка подниза со сложеност O(n*log n), ја го најдов на нет али ништо не разбрав

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> medali;
int N;
int min_wrong()
{
      int T[30000][3];
      switch(medali[0])
      {
            case 1:
                  T[0][0]=0;
                  T[0][1]=1;
                  T[0][2]=1;
                  break;
            case 2:
                  T[0][0]=1;
                  T[0][1]=0;
                  T[0][2]=1;
                  break;
            case 3:
                  T[0][0]=1;
                  T[0][1]=1;
                  T[0][2]=0;
                  break;
      }
      for(int i=1; i<N; i++)
      {
            switch(medali[i])
            {
                  case 1:
                        T[i][0]=T[i-1][0];
                        T[i][1]=min(T[i-1][0], T[i-1][1])+1;
                        T[i][2]=min(min(T[i-1][0], T[i-1][1]), T[i-1][2])+1;
                        break;
                  case 2:
                        T[i][0]=T[i-1][0]+1;
                        T[i][1]=min(T[i-1][0], T[i-1][1]);
                        T[i][2]=min(min(T[i-1][0], T[i-1][1]), T[i-1][2])+1;
                        break;
                  case 3:
                        T[i][0]=T[i-1][0]+1;
                        T[i][1]=min(T[i-1][0], T[i-1][1])+1;
                        T[i][2]=min(min(T[i-1][0], T[i-1][1]), T[i-1][2]);
                        break;
            }
      }
      return min(min(T[N-1][0], T[N-1][1]), T[N-1][2]);
}
int main()
{
      cin >> N;
      for(int i=0; i<N; i++)
      {
            int a;
            cin >> a;
            medali.push_back(a);
      }
      int m1=min_wrong();
      reverse(medali.begin(), medali.end());
      int m2=min_wrong();
      int m=min(m1, m2);
      cout << m << endl;       
}