Puoi leggere e provare a risolvere questo problema visitando questo indirizzo: vm.
Se in un certo istante (dopo aggiornamenti) è possibile aggiornare il programma , conviene farlo.
Dimostrazione: supponiamo che non sia ottimale aggiornare il programma . Si possono verificare due casi:
In una soluzione ottimale, non viene mai aggiornato dopo aggiornamenti. Si tratta di una contraddizione, perché inserendo alla soluzione ottimale l'aggiornamento di (come ()-esimo aggiornamento), senza cambiare l'ordine degli altri aggiornamenti, si ottiene una configurazione migliore.
Altrimenti, sia il primo aggiornamento di dopo aggiornamenti. È possibile ottenere un'altra soluzione ottimale spostando l'aggiornamento di dall'-esimo all'()-esimo, senza cambiare l'ordine degli altri aggiornamenti.
Notiamo che, se e i programmi con indice non possono più essere aggiornati, non può più essere aggiornato.
Quindi è possibile effettuare tutti gli aggiornamenti possibili (cioè ), in ordine dal programma al programma , e una volta aggiornato non si può più aggiornare nessun programma in .
Alla fine del processo, abbiamo raggiunto il numero ottimale di aggiornamenti. La complessità è .
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll aggiorna(int N, vector<int> A, vector<int> B) {
for (i = N - 2; i >= 0; i--) {
k = (A[i + 1] - A[i]) / B[i];
res += k; A[i] += (k * B[i]);
}
return res;
}