Zadanie z programowania dynamicznego

https://main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/pir/

Proszę o wskazówki jak się za to zabrać, rozumiem, że każda kolejna obliczona wartość musi bazować na poprzednich, ale póki co stworzyłem kilka rozwiązań dających podobny rezultat i duże odchylenie od poprawnych odpowiedzi ;v

Na pole n możesz wskoczyć z każdego z sześciu poprzednich pól, o ile na żadnym z nich nie ma pułapki. Liczba możliwości wskoczenia na pole n to suma możliwości wskoczeń na te sześć poprzednich pól.

Właśnie tez do tego doszedłem :/ ale mimo wszystko wyniki mam zle

Mocno nieoptymalne (tak sądzę), ale mam nadzieję, że poprawne dla małych wejść ;)
Spróbuj sobie podmieniać dane wejściowe (kliknij klonuj i edytuj stdin):

https://ideone.com/k1g2H3

Krwawy Samiec napisał(a):

Właśnie tez do tego doszedłem :/ ale mimo wszystko wyniki mam zle

a nie zapominałeś robić modulo k po każdym sumowaniu, a nie tylko na samym końcu?

bo sam algorytm(bez wczytywania) to będzie miał z 5 linijek i ciężko gdzieś indziej zrobić błąd, no chyba że indeksy ...

Spine napisał(a):

Mocno nieoptymalne (tak sądzę), ale mam nadzieję, że poprawne dla małych wejść ;)

Można dodać memoization przez wstawienie dwóch linii

import functools

@functools.lru_cache()
def rek(s, idx):

Robię wszędzie modulo k, mój algorytm jest iteracyjny i wykorzystuje sumy prefiksowe żeby można było się rozeznać ile wcześniejszych 6 pozycji nie zawiera w sobie pułapki.

Z resztą pokażę swój kod:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int getSum(vector<int> & prefix, int a, int b)
{
    if(a < 0)//gdyby sie okazalo ze i-6 jest ujemne
        a = 0;
    
    return prefix[b+1] - prefix[a];
}

int main(int argc, const char * argv[]) {
    
    int n,k;
    cin >> n >> k;
    
    char jumps[n];
    vector<int> prefix(n+1);
    prefix[0] = 0;
    
    for(int i = 0; i < n; i++)
    {
        cin >> jumps[i];
        if(jumps[i] == '1')
           prefix[i+1] = prefix[i] + 1;
       else
           prefix[i+1] = prefix[i];
    }
    
    vector<int> ways(1);//kolejne ilosci sposobów dojscia
    ways[0] = 1;//tj. start
    
    for(int i = 1; i < n; i++)
    {
        if(jumps[i] == '1')
        {
            ways.push_back(0);//nowa pozycja
            for(int j = 1; j <= getSum(prefix, i-6, i-1); j++)
                ways[ways.size()-1] = (ways[ways.size()-1]+ways[ways.size()-j-1])%k;//ilosc dojsc do nowej pozycji = suma dojsc do poprzednich pozycji oddalonych na odleglosc nie wieksza niz 6
        }
    }
    
    cout << ways[ways.size()-1] % k << endl;//ostateczny wynik
    
    return 0;
}

Już rozwiązane, problem polegał na tym, że przedtem ustawiałem zakres <i-6,i> zamiast <i-6,i-1> co zawierało w sobie obecną pozycję, ten kod wyżej jest poprawny, dziękuję wszystkim za zaangażowanie :D