Algoritmo del solitario del domino

Elaborato un approccio di programmazione dinamica al problema -

int t[n][2]; //Stores grid values
int b[n]; //Stores best solution upto a particular column
b[0]= t[0][1]-t[0][0]; //Compute score for first column (Absolute Value)
b[1]= Max (b[0] + Score for column 1 vertically, Score for first 2 horizontal columns);
for i=0...n 
  b[i]= Max ( b[i-1] + Score for column i vertically, b[i-2] + Score for horizontal columns i & i-1);
print b[n-1];

Funziona in modo efficiente sul data set dato, con una complessità temporale lineare!

Ecco un modo per affrontare / descrivere il problema:

Quando guardi la griglia 2xN, puoi vedere che ogni piastrellatura è definita in modo univoco nel seguente modo:

Per il blocco più a sinistra, verifica se è orizzontale o verticale. Quindi guarda il prossimo blocco.

Supponiamo che 2 supporti orizzontali e 1 supporti verticali il tuo Tiling 1 può essere scritto come: 121 mentre Tiling 2 può essere scritto come 22

Dato ogni vettore, il calcolo del costo totale dovrebbe essere semplice.

Ora puoi utilizzare questo algoritmo:

1. Trova una posizione di partenza (probabilmente il tuo algoritmo può fare il trucco qui)
2. Data una lunghezza della finestra (diciamo 5) prova tutte le combinazioni di uno e zero all'interno della finestra e calcola quale sia il miglioramento massimo.
3. Opzionale: esegui questo miglioramento
4. Sposta la finestra, quindi, invece di guardare le prime 5 colonne dispari, guarda ora le dispari da 2 a 6
5. Se non sei ancora alla fine, vai al passaggio 2, altrimenti esegui il miglioramento.
6. Facoltativo: se trovi miglioramenti, puoi andare al passaggio 1

Ecco l'implementazione in C ++ in O (n):

Usando la programmazione dinamica, stiamo costruendo dal basso verso l'alto, la soluzione migliore per ogni colonna.

I casi base sono le colonne 0 e 1:

Best [0] = > Il punteggio per i mini riquadri della colonna 0

Best [1] = > Il massimo di 2 possibili soluzioni impostate! (1. Accoppiamento saggio di file e  2. abbinamento con le colonne)

Altrimenti:

Best [n] = > Il massimo di 2 possibili soluzioni viene nuovamente impostato (1. La somma della nuova colonna e la soluzione migliore precedente B [n-1] 2. La somma della soluzione migliore B [n-2] e del nuovo riquadro di tessere 2x2 formata)

#include<iostream> 
using namespace std;
int abs(int n) { if(n < 0) return -1*n ; else return n; }

int main()
{
    int n, A[100001][2], B[100001], i, j;
    cin>>n;
    for(i=0;i<2;i++)
    {
        for(j=0;j<n;j++)
            cin>>A[j][i];
    }

    B[0] = abs(A[0][0] - A[0][1]);
    B[1] = max( B[0] + abs(A[1][0]-A[1][1]) , abs(A[1][0]-A[0][0])+abs(A[1][1]-A[0][1]) );
    for(i=2;i<n;i++)
        B[i] = max( B[i-1] + abs(A[i][0]-A[i][1]) , B[i-2] + abs(A[i][0]-A[i-1][0]) + abs(A[i][1]-A[i-1][1]) );

    cout<<B[n-1]<<endl;
    return 0;
}