Questo problema è più difficile di quello che sembra.
La mia idea era di partire dalla fine, vedere quanti utenti fossero connessi e calcolare quanto venisse speso fino alla disconnessione dell’ultimo utente, partire dal momento della disconnessione per cercare il costo di quello prima e così via, fino a K volte.
Però mi sono reso conto che non funziona così, perché seguendo questa strategia nel primo esempio avrei come consumo minimo 11 (mentre il risultato è 9):
Avrei gli upgrade a t=0(+2) avendo 8+3 = 11…
Come potrei risolvere questo problema? Qualche consiglio?
(Avevo pensato alla programmazione dinamica)
La programmazione dinamica è la strada giusta, prova a calcolare per ogni utente che si connette qual è la spesa minima che riesci a sostenere per ogni possibile K, dovresti capire come riutilizzare le soluzioni precedenti
Alla fin fine, se immaginiamo il problema in via geometrica, si tratta di “diminuire gli scalini”, e la potenza totale è l’area della figura. Ovvero, se il problema presenta 3 utenti che si connettono, e quindi 3 scalini, ma posso fare solo 2 upgrade, tento di eliminare uno scalino. Quale? Quello che mi aggiunge meno area possibile. Ovviamente devono essere scelti due scalini consecutivi, e facendo in modo che l’area aggiunta sia la minore possibile.
Una soluzione del genere è greedy, e non sempre le soluzioni greedy riescono a trovare la soluzione minima assoluta.
Nel caso in cui K = 2 e N = 3 sì, è intuitivo vedere che conviene fare la scelta greedy (in generale quando K = N - 1). Nel caso più generale però non è ovvio. Magari c’è in caso in cui, aumentando K di 1, l’insieme dei gradini da scegliere cambia completamente…
Se ho N= 7 e K=2, il ragionamento è ancora possibile.
Prima elimino uno scalino, poi ne elimino un’altro, poi un’altro ancora finché gli scalini rimasti non sono due. Poi calcolo l’area.
Sì il ragionamento è possibile ma non è ovvio vedere che l’area finale (dopo aver rimosso uno scalino alla volta) sia la minima possibile. Il punto è (ed è più o meno lo stesso per tutte le soluzioni greedy): cosa ti assicura che non ci sia un modo diverso di rimuovere gli scalini che ti permette di ottenere un’area ancora minore?
Con i giusti accorgimenti nel calcolare l’area che si aggiunge per ogni scalino probabilmente la complessità riesce ad essere minore dell’approccio dinamico, che però dovrebbe stare comunque dentro i tempi considerando le dimensioni ridotte dell’input.
Inoltre come diceva @wil93, siccome “togliere uno scalino” modifica anche il valore necessario per rimuovere gli scalini adiacenti, non sempre la scelta migliore ad ogni passaggio ti garantisce la soluzione migliore complessivamente.
Un modo per trovarlo può essere questo: una volta scritta la soluzione greedy, si generano tanti input (magari molto piccoli) e si confrontano gli output prodotti dalle due soluzioni. Se ti va di scrivere la greedy posso trovare un controesempio in questo modo anche se immagino che una volta scritta la greedy basta mandarla al correttore per vedere se è ottima o no
O magari invece è ottima e in tal caso non ci sono controesempi
Ora che ci penso, la soluzione greedy non è difficile da “eseguire a mano”. Posso provare a generare tipo 10 casi piccoli e risolverli a mano e con la soluzione ottima, e vedere se trovo una differenza. Torno subito
Ho provato ad implementare la soluzione di @erixstep e caricandola sul correttore fallisce i testcase 12, 14 e 15, prendendo 70/100.
Ora mi metto alla ricerca di un controesempio
Ho provato a risolverlo con la programmazione dinamica, parto dall’ultimo elemento e quando posso cerco di diminuire il carico del server, però ottengo solo 45/100 (i timeout sono diventati non corretti, tranne uno che è corretto)
EDIT: Ho sistemato anche nel codice, avevo dimenticato sizeof(int) nel memset, però ottengo due timeout, l’ultimo testcase del subtask 2 e del subtask 4
anche se immagino che una volta scritta la greedy basta mandarla al correttore per vedere se è ottima o no 
