Dichiarazione di non responsabilità: il metodo descritto di seguito non è universale, ma spesso può risolvere un problema o aiutarti a trovare la soluzione giusta.
Se il problema si riduce al fatto che è necessario suddividere l'array in sottosegmenti non intersecanti (una sequenza di elementi consecutivi) in modo ottimale (o contare il numero di suddivisioni adatte), allora vale la pena provare a risolverlo utilizzando la programmazione dinamica.
Uno schema di soluzione di esempio è il seguente:
dp[i] - risposta per i primi i elementi
Contando dp[i]: poiché stiamo considerando solo i primi i elementi, l'i-esimo elemento sarà l'ultimo, il che significa che questo elemento sarà nell'ultimo sottosegmento e, allo stesso tempo, quello più a destra lì. Pertanto, possiamo iterare sul limite sinistro dell'ultimo sottosegmento j. Nel processo di enumerazione, calcoleremo il valore di questo sottosegmento e, se è corretto, ricalcoleremo da dp[i] a dp[j - 1] e il valore del sottosegmento [j;i].
Considera il seguente semplice problema: dato un array di numeri interi, devi dividerlo nel numero minimo di sottosegmenti non intersecanti in modo che ogni numero sia incluso in qualche sottosegmento e che ogni sottosegmento contenga gli stessi numeri. Ad esempio, per un array 1 2 2 3 3 3 2 1 1, la partizione ottimale è la seguente: [1] [2 2] [3 3 3] [2] [1 1]. Questo compito è facilmente risolvibile semplicemente passando attraverso l'array (mettiamo tutti gli stessi elementi consecutivi in un sottosegmento), ma lo risolveremo usando la programmazione dinamica per un esempio.
int;
cin>> N;
// riempie l'array con 1 indice
vettore arr(n + 1);
per (int i = 1; i <= n; i++)
cin>> ar[i];
// inizialmente imposta +oo sui valori dp
vettore dp(n + 1, 1000000000);
// non è necessario dividere un array di lunghezza zero, quindi la risposta è 0
dp[0] = 0;
// conta la risposta per dp[i] in i crescente
for (int i = 1; i <= n; i++) {
// attualmente arr[i] è l'ultimo elemento, quindi sarà il numero più a destra nell'ultimo sottosegmento
// passa in rassegna tutte le opzioni relative a dove è iniziato l'ultimo sottosegmento
for (int j = i; j > 0; j--) {
if (arr[j] != arr[i]) {
// se incontri un elemento che non è uguale all'ultimo, il sottosegmento conterrà numeri diversi e questo non soddisfa la condizione
// non ha senso continuare, perché spostando il bordo sinistro a sinistra, questo elemento non scomparirà, quindi lo rompiamo
rottura;
}
// immagina che l'ultimo sottosegmento fosse [j;i]
// quindi devi prendere la partizione ottimale dei primi j-1 elementi e aggiungere 1 (il sottosegmento [j; i] stesso)
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
Se gli elementi potrebbero non appartenere a nessuno dei sottosegmenti, allora devi solo considerare l'opzione appropriata, come dp[i] = dp[i - 1]
|
Se è necessario dividere l'array in esattamente k sottosegmenti, il secondo parametro viene semplicemente aggiunto nella programmazione dinamica: in quanti segmenti suddividere.
Cioè, ora considereremo il seguente dp:
dp[i][j] è la risposta per i primi i elementi, se li dividiamo esattamente in j segmenti.
Fai attenzione agli stati non validi.
Il ricalcolo della dinamica è lo stesso, ma tenendo conto del secondo parametro. Cioè, contando dp[i][k] e ordinando attraverso il bordo sinistro dell'ultimo sottosegmento j, ricalcoliamo da dp[i][k] a dp[j - 1][k - 1] e il valore del segmento [j;io].
|
Dichiarazione di non responsabilità: il metodo descritto di seguito non è universale, ma spesso può risolvere un problema o aiutarti a trovare la soluzione giusta.
Se c'è una serie di spazi posizionati su un asse (di solito l'asse del tempo o gli indici di un array) e devi sceglierne alcuni in modo ottimale in modo che gli spazi selezionati non si intersechino, allora dovresti provare a utilizzare la programmazione dinamica .
Schema approssimativo della soluzione:
Inizialmente, ordiniamo gli spazi disponibili in base al bordo destro. Iniziamo con le seguenti dinamiche: dp[i] - la risposta per i primi intervalli i.
Ricalcoleremo come segue: in primo luogo, consideriamo la situazione in cui questo intervallo non verrà utilizzato, quindi solo dp[i] = dp[i-1]. Si noti che ciò garantisce che i valori di dp[i] non diminuiscano al crescere di i. E questo è logico, perché. aggiungendo un nuovo divario, non possiamo peggiorare la risposta globale: o semplicemente ignoriamo il nuovo divario o costruiamo una variante più redditizia utilizzandolo. Ora, se vogliamo usare l'intervallo i-esimo, allora possiamo usare quegli spazi i cui bordi a destra sono minori del bordo sinistro dell'intervallo corrente, poiché dobbiamo scegliere un insieme di spazi non sovrapposti. Per fare ciò, inizialmente abbiamo ordinato gli spazi in base al bordo destro, in modo che ora possiamo trovare in modo efficiente la posizione richiesta. Questo può essere fatto analiticamente, se possibile, ma nel caso generale è possibile trovare un gap con un binsearch, il cui bordo destro è minore del bordo sinistro di quello attuale e, allo stesso tempo, il massimo possibile uno. Vogliamo massimizzare il confine giusto per motivi avidi, perché man mano che cresco, la risposta non può che aumentare. Di conseguenza, troviamo la posizione richiesta p e ricalcoliamo da dp[i] a dp[p] e l'i-esimo intervallo.
|