Aiuto per Pranzo dalla nonna (ois_nonna)

Aiuto
1

E’ da un po’ di tempo che sto provando a risolvere il problema “Pranzo dalla Nonna”, il punteggio massimo che sono riuscito ad ottenere è di 80/100, sbagliando completamente la subtask numero 5. Qualcuno mi può aiutare?

image
image1202×433 14.7 KB

Ecco il mio codice:

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <assert.h>

using namespace std;

#define MAXN 5000
#define MAXK 5000
#define MAXP 1000000

int dp[MAXN][MAXK];
int P[MAXN];
int N, K;

int mangia(int porz, int mang, int P[]) {

    if (mang >= K) return mang;
    if (porz == N) return mang;

    if (dp[porz][mang] != -1) return dp[porz][mang];

    dp[porz][mang + P[porz]] = mangia(porz + 1, mang + P[porz], P);
    
    dp[porz][mang] = mangia(porz + 1, mang, P);

    dp[porz][mang] = min(dp[porz][mang + P[porz]], dp[porz][mang]);

    if (dp[porz][mang] < K) { dp[porz][mang] = max(dp[porz][mang + P[porz]], dp[porz][mang]); }

    return dp[porz][mang];

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    memset(dp, -1, sizeof(dp));

    FILE *fr, *fw;
    int i;

    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");

    //cin >> N >> K;
    assert(2 == fscanf(fr, "%d %d", &N, &K));

    for(i = 0; i < N; i++) {

        //cin >> P[i];
        assert(1 == fscanf(fr, "%d", &P[i]));

    }

    //cout << mangia(0, 0, P);
    fprintf(fw, "%d\n", mangia(0, 0, P));

    fclose(fr);
    fclose(fw);

    return 0;

}

Grazie mille in anticipo!

2

ho risolto!, il problema stava qua:

dp[porz][mang + P[porz]] = mangia(porz + 1, mang + P[porz], P);
dp[porz][mang] = mangia(porz + 1, mang, P);

Qua sto scrivendo su una cella che “non abbiamo ancora visitato”.

Quindi la funzione mangia corretta è:

int mangia(int porz, int mang, int P[]) {

    if (mang >= K) return mang;
    if (porz == N) return mang;

    if (dp[porz][mang] != -1) return dp[porz][mang];

    int prendi= mangia(porz + 1, mang + P[porz], P);
    
    int lascia= mangia(porz + 1, mang, P);

    dp[porz][mang] = min(prendi, lascia);

    if (dp[porz][mang] < K) { dp[porz][mang] = max(prendi, lascia); }

    return dp[porz][mang];

}