Aiuto con Nonna 60/100

Buonasera, avrei un problema con questo codice, ho utilizzato la programmazione dinamica come consigliato da AlgoBadge ma non riesco a trovare alcun bug. C’è un testcase in cui mi sbaglia l’output e un altro in cui supera il limite di tempo. Cosa potrei fare per migliorarlo?? Allego in seguito il codice.

#include <bits/stdc++.h>
using namespace std;
#define MAXP 1000005
int P[MAXP];
FILE *fr, *fw;

int mangia(int N, int K, int P[]) {
vector<int> dp(200001, INT_MAX); // vettore di supporto per la programmazione dinamica
dp[0] = 0; // inizializzazione

for (int i = 0; i < N; i++) {
    for (int j = 200000 - P[i]; j >= 0; j--) { // scorriamo il vettore dp partendo da 200000 - P[i] per evitare di sovrascrivere dati utili
        if (dp[j] != INT_MAX) { // se abbiamo gia' trovato una soluzione per il peso j, possiamo calcolare una soluzione per il peso j + P[i]
            dp[j + P[i]] = min(dp[j + P[i]], dp[j] + 1);
        }
    }
}

for (int i = K; i <= 200000; i++) { // restituiamo il primo indice del vettore dp in cui abbiamo trovato una soluzione valida
    if (dp[i] != INT_MAX) {
        return i;
    }
}

return -1; // se non abbiamo trovato soluzioni valide
}

int main() {
    int N, K;
    
    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    assert(2 == fscanf(fr, "%d %d", &N, &K));
    for(int i=0; i<N; i++){
    	assert(1 == fscanf(fr, "%d", &P[i]));
	}
           

	fprintf(fw, "%d\n", mangia(N, K, P));
	 	
    fclose(fr);
    fclose(fw);
    return 0;
}

Buongiorno, credo che con questo caso:

1 100
1000000

Il tuo codice ritorni -1, mentre dovrebbe ritornare 1000000. Ti consiglio di considerare i P_i \ge K a parte.
Inoltre il limite di 2\cdot 10^5 sulla dp mi sembra molto arbitrario e può essere diminuito.

C’è anche una soluzione che non tratta i P_i \ge K a parte:

#define maxp 1000010 //in generale maxp dovrebbe essere il massimo tra il massimo dei P_i + 1 e K*2

int mangia(int N, int K, int P[]) {
    
    bitset<maxp> dp;
    dp[0] = 1;
    
    for (int i = 0; i < N; i++) {
        dp |= dp << P[i];
    }
    
    for (int i = K; i < maxp; i++) {
        if (dp[i]) {
            return i;
        }
    }
    
    return -1;
}

Bitsets

Potresti spiegarmi cosa fa il primo ciclo for?? Che considerazione hai fatto per mettere dp | dp??

L’operatore | significa l’or bit a bit, scrivere dp |= dp << P[i] è (quasi) come scrivere dp = dp | (dp << P[i]), se non hai familiarità con le operazioni bit a bit ti consiglio di leggerti la parte uno di quel blog.

Se la tua domanda era più concettuale la considerazione che ho fatto è che in dp[i] non c’è bisogno di salvarsi il numero minimo di portate che totalizzano i grammi, ma solo se si possono totalizzare o meno.

Va bene, grazie mille.

1 Mi Piace