[85/100] su Dog Trick Competition

Aiuto
1

Buonasera,

purtroppo non riesco a passare un test case del secondo subtask di Dog Trick

image

Questo è il codice che ho scritto:

int score_ric(const vector<int> &t, int i, bool can_skip) {

  if (i >= t.size()) return 0;

  // Check if the result is already in the memo
  if (memo[can_skip * n + i] != 0) {
      return memo[can_skip * n + i];
  }

  const pair<int, int> trick = make_pair(t[i], t[i + 1]);
  const pair<int, int> trick2 = make_pair(t[i], t[i + 2]);

  int can_perform_first_trick = (i + 1 >= t.size() && t[i] != (k + 1)) || tricks.find(trick) != tricks.end() ? 1 : 0;
  int can_perform_second_trick = (i + 2 >= t.size() && t[i] != (k + 1)) || tricks.find(trick2) != tricks.end() ? 1 : 0;

  int best_score = 0;

  if (can_perform_first_trick == 0 && can_perform_second_trick == 0) {
      if (can_skip) {
          best_score = score_ric(t, i + 1, false);
          memo[can_skip * n + i] = max(best_score, memo[can_skip * n + i]);
          return best_score;
      } else {
          return 0;
      }
  }

  if (can_perform_first_trick == 1) {
      if (can_skip) {
          best_score = max(1 + score_ric(t, i + 1, true), score_ric(t, i + 1, false));
      } else {
          best_score = 1 + score_ric(t, i + 1, true);
      }
  }

  if (can_perform_second_trick == 1) {
      if (can_skip) {
          best_score = max(max(1 + score_ric(t, i + 2, true), score_ric(t, i + 2, false)), best_score);
      } else {
          best_score = max(1 + score_ric(t, i + 2, true), best_score);
      }
  }

  // Save the result in memo before returning
  memo[can_skip * n + i] = max(best_score, memo[can_skip * n + i]);

  return best_score;
}

dove memo è un vettore di interi

2

Il tuo codice sembra sbagliare in alcuni casi i task con K = 1, come puoi verificare con questo input:

6 1
1 1 1 2 2 2
2
2 2
1 2

che restituisce 3 se ho correttamente letto il codice, in quanto incompleto, invece di 0.
Una soluzione banale al problema potrebbe essere quella di trattare il caso speciale K = 1 separatamente con una procedura iterativa in quanto abbastanza semplice e facile da implementare.

3

Ciao!
Prima di tutto grazie della risposta è stata davvero utile, ho visto il tuo test di esempio e mi è sembrato strano dati i vincoli delle coppie:
image

allora ho comunque provato il tuo test ma modificandolo così:

6 1
1 1 1 2 2 2
1
1 1

ed ottenevo 2 invece che 0… con mio enorme sconforto ho realizzato che la soluzione che ho condiviso non rispetta la condizione del cortocircuito dovuto da 2 trick consecutivi saltati

Ho cambiato totalmente approccio ed adesso ho ottenuto 100/100, grazie ancora