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