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]