Misolovke - DP

Pitanja i problemi
1

Pitanje ili opis problema

Zdravo,
Radio sam problem “Misolovke” iz oblasti Dinamicko Programiranje. Neko vreme sam pokusavao da nadjem gresku u kodu ali nisam uspeo. Naime, ovaj kod pada na samo jednom test primeru dok svi ostali daju “OK”. Moze li neko da mi pomogne?
Evo koda:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


vector<ll> sufmax, prefmax, suma;
ll a[270][270], dp[270][270][2], max0, max1;
ll n, k;

int main()
{
    cin >> n >> k;
    for(int i =0 ; i < n; ++i){
        for(int j = 0; j < n; ++j){
            cin >> a[i][j];
        }
    }
    suma.resize(n+1, 0);
    //for(int j = 0; j < n-k+1; ++j){
    //    for(int e = j; e < j+k; ++e){
    //        suma[j] += a[0][e];
    //    }
        //cout << suma[j] << " ";
    //}
    //cout << "\n";
    prefmax.clear();
    sufmax.clear();
    prefmax.resize(n+1, -1e9);
    sufmax.resize(n+1, -1e9);
    
    for(int i = 0; i < n-k+1; ++i){
        for(int j = i; j < i+k; ++j){
            dp[0][i][1] += a[0][j];
            //if(i) dp[0][i][0] += a[0][j];
        }
        //prefmax[i] = dp[0][i][1];
        //if(i){
        //    prefmax[i] = max(prefmax[i-1], prefmax[i]);
        //}
        max0 = max(max0, dp[0][i][0]);
        max1 = max(max1, dp[0][i][1]);
    }
    for(int j = k-1; j < n; ++j){
        if(j > k-1){
            prefmax[j]= max(prefmax[j-1], dp[0][j-k+1][1]);
        } else {
            prefmax[j] = dp[0][j-k+1][1];
        }
    }
    //cout << max0 << " " << max1 << "\n";
    for(int i = n-k; i >= 0; --i){
        if(i == n-k){
            sufmax[i] = dp[0][i][1];
            continue;
        }
        sufmax[i] = max(dp[0][i][1], sufmax[i+1]);
    }
    //MAIN LOOP -----------------------------------------------
    for(int i = 1; i < n; ++i){
        for(int j = 0; j < n; ++j){
            suma[j] = 0;
        }
        for(int j = 0; j < n-k+1; ++j){
            for(int e = j; e < j+k; ++e){
                suma[j] += a[i][e];
            }
        }
        //for(int j =0; j < n; ++j){
        //    cout << prefmax[j] << " " << sufmax[j] << " ";
        //}
        //cout << "\n";
        for(int j = 0; j < n-k+1; ++j){
            if(j < n-k){
                dp[i][j][0] = max(dp[i][j][0], sufmax[j+k+1]);
            }
            if(j){
                dp[i][j][0] = max(prefmax[j-1], dp[i][j][0]);
            }
            dp[i][j][0] = max(dp[i][j][0], max0);
            dp[i][j][0] += suma[j];
            dp[i][j][1] = max(max1,max0) + suma[j];
            //cout << dp[i][j][0] << " ";
        }
        //cout << "\n";
        for(int j = 0; j <=n; ++j){
            prefmax[j] = -1e9;
            sufmax[j] = -1e9;
        }
        for(int j = k-1; j < n; ++j){
            if(j > k-1){
                prefmax[j]= max(prefmax[j-1], dp[i][j-k+1][1]);
            } else {
                prefmax[j] = dp[i][j-k+1][1];
            }
        }
        for(int j = n-k; j >= 0; --j){
            if(j == n-k){
                sufmax[j] = dp[i][j][1];
                continue;
            }
            sufmax[j] = max(dp[i][j][1], sufmax[j+1]);
        }

        //cout << "\n";
        max0 = -1e9;
        max1 = -1e9;
        for(int j = 0; j < n; ++j){
            max0 = max(max0, dp[i][j][0]);
            max1 = max(max1, dp[i][j][1]);
        }
    }
    // END OF THE MAIN LOOP -----------------------------------------------
    ll ans = -1e9;
    for(int i = 0; i < n; ++i){
        ans = max(ans, dp[n-1][i][0]);
    }
    cout << ans << "\n";
    return 0;
}

Hvala,
Momcilo Tosic

P.S. dp[i][j][0] je optimalno resenje ako u itom redu uzimamo misolovke redom od jte, a mis ne moze doci u iti red. dp[i][j][1] je slucaj kad mis moze doci u iti red (takodje od jte uzimamo misolovke u itom redu)

Link ka zadatku ili odgovarajućoj stranici

https://petlja.org/BubbleBee/r/Problems/Misolovke

2

Mislim da ti ne radi jer nemas dovoljno stejtova u dp. Probaj dp[i][j][fromLeft][fromRight] -> fromLeft je 0 ako ne moze doci do polja levog od j, a 1 ako moze. fromRight je 0 ako ne moze doci do polja desno od j+k-1 , a 1 ako moze. i,j su isti kao kod tebe (Nisam jos probao, ovo mi je prvo palo na pamet)

3

I onda je resenje max(dp[n][j][0][0]) za svako j