Ho provato a risolvere il problema partita (su terry). Inizialmente ho applicato solamente una ricorsione molto semplice che pero era troppo lenta, poi ho provato con dp ma qui ci sono gli errori. Quello che non capisco e’ che se MAXN e MAXK sono piccoli allora funziona altrimentri mi da “Error: value of 000000ba487bf7c7 too large for field of 4 bytes at 0000000000000387”. Qualche chiarimento?
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 100000
#define MAXK 1000001
vector <int> R(MAXN);
int memo[MAXN][MAXK];
int partita(int index, int N, int K){
// se i soldati sono finiti imposto il risultato altissimo
if (K == 0)
return 10000000;
if (index == N)
return 0;
if (memo[index][K] != 0)
return memo[index][K];
if (R[index] == 0)
// non potendo prendere rinforzi passo direttamente al prossimo
memo[index][K] = partita(index+1, N, K-1);
else
// se prendo i rinforzi aumento di 1 altrimenti niente
memo[index][K] = min(partita(index+1, N, K-1+R[index]) +1, partita(index+1, N, K-1));
return memo[index][K];
}
void solve(int t) {
int N, K, i;
cin >> N >> K;
for (i = 0; i < N; i++) cin >> R[i];
int risposta = partita(0, N, K);
// se non si e' mai trovato neanche un percorso che portasse alla fine
// stampo -1
if (risposta == 10000000)
risposta = -1;
cout << "Case #" << t << ": " << risposta << "\n";
//resetto memo tutto a zero
/*for (i = 0; i < N; i++){ //fatto cosi non va bene e non so perche
for (int j = 1; j <= K; j++){
memo[i][j] = 0;
}
}*/
// mentre cosi funziona
for (i = 0; i < MAXN; i++){
for (int j = 1; j <= MAXK; j++){
memo[i][j] = 0;
}
}
}
int main() {
freopen("partita_input_1.txt", "r", stdin);
freopen("partita_output_1.txt", "w", stdout);
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
solve(t);
}
return 0;
}