Frog 1

Solution by TheRealFertos — 100 pts

Code / Notes

#include <bits/stdc++.h>
using namespace std;

int forcatotal=0;
// Guardar a resposta pra cada situação possível
// memo = {-1, -1, -1, -1}

// Sempre que chamar com o mesmo q, vai dar a mesma resposta
// então guarda a resposta pra cada q
// la embaixo coloca (N, -1)
vector <int> memo;
int PULA (int q, vector<int> &v) {
    if (q == v.size()-1) {
        return 0;     
    }
    if(q == v.size()-2) {
        return abs(v[q+1]-v[q]);
    }
    if (memo[q] != -1) {
        return memo[q]; 
    }
    int pula1=abs(v[q+1]-v[q])+PULA(q+1,v);
    int pula2=abs(v[q+2]-v[q])+PULA(q+2,v);
    return memo[q] = min(pula1,pula2);
}

// PULA(3) { ... memo[3] = 10; return 10; }

// 1. Ver as transições (pular e ver o mínimo)
// 2. Ver o caso base
// --- checa se funciona (nos "samples"/exemplos)
// 3. Guardar a resposta (memo)

int main () {
    int n;
    cin >> n;
    memo.assign(n, -1);
    vector <int> forcanecessaria(n);
    for (auto &x : forcanecessaria) {
        cin >> x;
    }
    cout << PULA(0,forcanecessaria);
}

Last updated 1 month, 1 week ago

« Back to problem