Monopoly- DP ricorsiva

Sto provando a risolvere il problema monopoly con ricorsione e programmazione dinamica, l’idea é semplice: per ogni combinazione casella i visitata in un certo turno j ricerco il massimo tra le caselle dalla i-2 alla i-12 (i valori ottenibili con due dadi vanno da 2 a 12) visitate nel turno j-1. Cerco anche il massimo tra le caselle dalla i-2 alla i-12 considerando solo i valori pari del dado (ottenibili con due facce uguali) e mi assicuro che questa operazione non venga fatta piú di 3 volte. Probabilmente l’errore sta nel fatto che non sfrutto il dato sottolineato dal problema, cioé che ottenendo 2 e 12 sono obbligato a tirare di nuovo i dati (non ho idea di come usarlo)


#include <fstream>
#include <iostream>
#include <vector>

#define MAXN 1001

using namespace std;

// input data
int N, K;
vector<int> T;
int DP[MAXN][MAXN];
bool visto[MAXN][MAXN];

int maxi(int a,int b){
    if(a>b)return a;
    return b;
}

int monopoli(int i,int N,int j,int K,int c){
    if(j==0 or visto[i][j]){
        visto[i][j]=true;
        return DP[i][j];
    }else{
        int massimo=INT_MIN;
        for(int a=2;a<=12;a++){                 //itero sulle caselle dalle quali posso arrivare con un solo tiro
            int m=i-a;
            if(m<=0)m+=N;
            massimo=maxi(massimo,monopoli(m,N,j-1,K,0)+T[i]);
        }
        if(c<3){                                //itero sulle caselle dalle quali posso arrivare con un tiro doppio/triplo
            for(int a=2;a<=12;a=a+2){
                int m=i-a;                      //N-1 é adicente a 0
                if(m<0)m+=N;
                massimo=maxi(massimo,monopoli(m,N,j,K,c+1)+T[i]);
            }
        }
        DP[i][j]=massimo;
        visto[i][j]=true;
        return DP[i][j];
    }


}

int main() {
    //  uncomment the following lines if you want to read/write from files
    ifstream cin("input.txt");
    //ofstream cout("output.txt");

    cin >> N >> K;
    T.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> T[i];
    }


    int ris = monopoli(N,N,K,K,0);


    for(int i=0;i<N+1;i++){
        for(int j=0;j<K+1;j++){
            cout<<DP[i][j]<<"\t";
        }
        cout<<endl;
    }

    cout << ris << endl;  // print the result
    return 0;
}

digita o incolla il codice qui

Siccome quando escono due dadi uguali deve ripetere il lancio dei dadi oer un massimo di 3 volte nella tua tabella degli stati devi tenere conto anche di questa eventualità, che non ripete alcun lancio, che ne ripete il primo e ne ripete il secondo. Quindi la tua tabella dp[MAXN][MAX] dovrebbe essere dp[MAXN][MAXN][3] per considerare anche la ripetizione dei lanci.

Ho fatto qualche modifica e corretto qualche bug evidente (inizializzazione a 0 della matrice DP quando possono esistere anche risultati negativi, chiamata della funzione ricorsiva con N e non N-1), ma continua a non funzionare

// NOTE: it is recommended to use this even if you don't understand the following code.

#include <fstream>
#include <iostream>
#include <vector>

#define MAXN 1001

using namespace std;

// input data
int N, K;
vector<int> T;
int DP[MAXN][MAXN][3];
bool visto[MAXN][MAXN][3];


int monopoli(int i,int N,int j,int K,int c){
    if(visto[i][j][c]){                         //casi base fissati nel main
        return DP[i][j][c];
    }else{
        int massimo=INT_MIN;
        for(int a=2;a<=12;a++){                 //itero sulle caselle dalle quali posso arrivare con un solo tiro
            int m=i-a;
            if(m<0)m+=N;
            massimo=max(massimo,monopoli(m,N,j-1,K,0)+T[i]);
        }
        if(c<2){                                //itero sulle caselle dalle quali posso arrivare con un tiro doppio/triplo
            for(int a=2;a<=12;a=a+2){
                int m=i-a;                      //N-1 é adicente a 0
                if(m<0)m+=N;
                massimo=max(massimo,monopoli(m,N,j,K,c+1)+T[i]);
            }
        }
        DP[i][j][c]=massimo;
        visto[i][j][c]=true;
        return DP[i][j][c];
    }


}

int main() {
    //  uncomment the following lines if you want to read/write from files
    ifstream cin("input.txt");
    //ofstream cout("output.txt");

    cin >> N >> K;
    T.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> T[i];
    }

    for(int i=0;i<N;i++)
        for(int j=0;j<K+1;j++)
            for(int c=0;c<3;DP[i][j][c++]=INT_MIN){
                if(j=0){
                    DP[i][j][c]=0;
                    visto[i][j][c]=true;
                }
            }

    int ris = max(monopoli(N-1,N,K,K,0),monopoli(N-1,N,K,K,1));
    ris = max(ris,monopoli(N-1,N,K,K,2));


    for(int i=0;i<N;i++){
        for(int j=0;j<K+1;j++){
            for(int c=0;c<3;c++)
                cout<<DP[i][j][c]<<"|";
            cout<<"\t";
        }
        cout<<endl;
    }

    cout << ris << endl;  // print the result
    return 0;
}

Qui una soluzione di monopoly usando come base il tuo programma, ho cercato di mettere piu’ commenti possibili. Se non capisci qualcosa scrivimi senza problemi :smile:

#include <fstream>
#include <iostream>
#include <vector>
#include <climits>
#include <string.h>

#define MAXN 1001

typedef long long ll;

using namespace std;

//ho cambiato tutto a long long perche' ci potrebbero essere risultati maggiori dei valori int
int N, K;
vector<int> T;
ll DP[MAXN][MAXN][3];

//gli stati del dp sono: la posizione in cui ci troviamo; il numero di quante volte abbiamo fatto doppio; e il numero del turno;
ll monopoli(int posizione, int num_doppi, int turno) {
	if(turno == K) return 0; //L'unica condizione di uscita, se i turni finiscono
	if(num_doppi == 3) return monopoli(posizione, 0, turno + 1); //se invece dobbiamo andare avanti di turno, resettiamo i doppi
	
    if(DP[posizione][turno][num_doppi] != -1) { //controlliamo se lo abbiamo gia' calcolato
        return DP[posizione][turno][num_doppi];
    }
    
    ll massimo=LONG_LONG_MIN;
    for(int dado_0 = 1; dado_0 <= 6; ++dado_0) { // in questi 2 for calcoliamo tutte le combinazioni di numeri
    	for(int dado_1 = 1; dado_1 <= 6; ++dado_1) {
    		int aggiungere = (dado_0 + dado_1 + posizione) % N; //la prossima posizione dove andare
    		if(dado_0 == dado_1) massimo = max(massimo, monopoli(aggiungere, num_doppi + 1, turno) + T[aggiungere]); //se i dadi sono doppi
    		else massimo = max(massimo, monopoli(aggiungere, 3, turno) + T[aggiungere]); // se non sono doppi
		}
	}
	
    DP[posizione][turno][num_doppi] = massimo; //salviamo il dp
    return massimo;
}

int main() {
    ifstream cin("input.txt");
    //ofstream cout("output.txt");

    cin >> N >> K;
    T.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> T[i];
    }

    memset(DP, -1, sizeof DP); //questa funziona setta tutti i valori dell'array 3d a -1
    //i parametri sono, l'array, il valore da inserire, la grandezza dell'array
	            
    cout << monopoli(0, 0, 0) << endl;
    return 0;
}