# Aiuto con Nonna 60/100

**URL:** <https://forum.olinfo.it/t/aiuto-con-nonna-60-100/8174>\
**Category:** Aiuto\
**Created:** [11 Aprile 2023, 8:20pm UTC](https://forum.olinfo.it/t/aiuto-con-nonna-60-100/8174 "2023-04-11T20:20:59Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Fearingtable](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fearingtable/32/2780_2.png) [@Fearingtable](https://forum.olinfo.it/u/Fearingtable)\
**Post date:** [11 Aprile 2023, 8:20pm UTC](https://forum.olinfo.it/t/aiuto-con-nonna-60-100/8174/1 "2023-04-11T20:20:59Z")

</div>

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.

```auto
#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;
}

```

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [12 Aprile 2023, 8:28am UTC](https://forum.olinfo.it/t/aiuto-con-nonna-60-100/8174/2 "2023-04-12T08:28:45Z")

</div>

Buongiorno, credo che con questo caso:

```auto
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:

```auto
#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](https://codeforces.com/blog/entry/73558)

---

<div class="post-metadata">

**Author:** ![Fearingtable](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fearingtable/32/2780_2.png) [@Fearingtable](https://forum.olinfo.it/u/Fearingtable)\
**Post date:** [12 Aprile 2023, 12:01pm UTC](https://forum.olinfo.it/t/aiuto-con-nonna-60-100/8174/3 "2023-04-12T12:01:53Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![simpatine](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simpatine/32/444_2.png) [@simpatine](https://forum.olinfo.it/u/simpatine)\
**Post date:** [12 Aprile 2023, 12:43pm UTC](https://forum.olinfo.it/t/aiuto-con-nonna-60-100/8174/4 "2023-04-12T12:43:29Z")

</div>

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](https://codeforces.com/blog/entry/73490) di [quel blog](https://codeforces.com/blog/entry/73558).

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.

---

<div class="post-metadata">

**Author:** ![Fearingtable](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fearingtable/32/2780_2.png) [@Fearingtable](https://forum.olinfo.it/u/Fearingtable)\
**Post date:** [12 Aprile 2023, 1:02pm UTC](https://forum.olinfo.it/t/aiuto-con-nonna-60-100/8174/5 "2023-04-12T13:02:39Z")

</div>

Va bene, grazie mille.