/* Batch (IOI 2002) Copyright (C) 2002 Paolo Boldi and Sebastiano Vigna This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Per capire la soluzione di questo problema è utile una rappresenzazione geometrica dei dati. Disegnate, sul piano cartesiano, tanti rettangoli quanti sono i compiti. Ogni rettangolo ha una base pari al costo del compito e un'altezza pari al tempo di elaborazione del compito; il primo rettangolo (quello relativo al primo compito) ha l'angolo in basso a sinistra coincidente con l'origine degli assi. Ogni compito successivo ha l'angolo in basso a sinistra coincidente con l'angolo in alto a destra del compito (rettangolo) precedente. ******************* * * ********************* * * ********** * * * * *********** * * * * * * ************* * * ********** Assumiamo, per il momento, che il tempo di inizializzazione sia 0. Supponete di aver già deciso come raggruppare i vari compiti in blocchi. Nel nostro esempio, supponiamo di aver deciso i blocchi {1,2},{3},{4,5}. 3 --******************* |,*.................* ********************* 2 *.*.................. **********.................. *......*.................... 1 *......*.................... ---------***********.................... |,,,,,,,,*..*........................... |,,,,,,,,*..*........................... |,,,,,,,,*..*........................... *************........................... *........*..|........................... **********--|........................... Come si vede, il costo che compete a ogni blocco è ottenibile delimitando il blocco in un rettangolo verticale (nella figura, i loro angoli in alto a sinistra sono indicati con 1, 2, 3) e calcolandone l'area. Notate che parte di quest'area è un costo fisso, indipendentemente da come sono stati piazzati i blocchi (è la parte di area indicata con i "."), mentre una parte (quella indicata con ",") dipende dal raggruppamento in blocchi. In effetti, dobbiamo anche considerare i tempi di inizializzazione. Questo significa che ogni volta che iniziamo un nuovo blocco dobbiamo "alzare" la figura di un'altezza pari al tempo di inizializzazione S. 3 --******************* |,*.................* ********************* *.*.................. xxxxxxxxxxxxxxxxxxxxx 2 xxxxxxxxxxxxxxxxxxxxx **********.................. *......*.................... *......*.................... xxxxxxxxxxxxxxxxxxxxxxxxxxxx 1 xxxxxxxxxxxxxxxxxxxxxxxxxxxx ---------***********.................... |,,,,,,,,*..*........................... |,,,,,,,,*..*........................... |,,,,,,,,*..*........................... *************........................... *........*..|........................... **********--|........................... xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx I costi sono rappresentati dalle "x" nella figura precedente. Notate che il costo addizionale dovuto all'aggiunta di un blocco che parte immediatamente prima del compito i è pari a S moltiplicato per la somma dei costi dei compiti successivi. Con questa rappresentazione in mente, il seguente algoritmo (basato sulla programmazione dinamica) dovrebbe risultare chiaro. */ #include #include #include const int MAX_COMP = 10000; using namespace std; int N, S; // Numero di compiti e tempo di inizializzazione. int costo[ MAX_COMP ]; // Costo di ogni compito. int tempo[ MAX_COMP ]; // Tempo di elaborazione di ogni compito. int ott[ MAX_COMP + 1 ]; // Nella posizione i, ottimo dei primi i compiti. int Stot[ MAX_COMP + 1 ]; // Nella posizione i, contributi alla sommatoria // dovuti ai tempi di inizializzazione in // corrispondenza all'i-esimo compito. int main(int argc, char *argv[]) { int i, j, t, c, tempi; /* Leggiamo l'input. */ cin >> N >> S; for( i = 0; i < N; i++ ) cin >> tempo[i] >> costo[i]; /* Calcoliamo i costi cumulativi. Se spezziamo la sequenza subito prima del compito i causiamo un incremento di costo pari alla somma dei costi dei compiti successivi a i moltiplicata per S (c'è anche un costo S * costo[i] che verrà aggiunto durante la fase di riempimento di ott). */ for( i = N - 2; i >= 0; i-- ) Stot[ i ] += Stot[ i + 1 ] + costo[ i + 1 ] * S; for( i = 0; i < N; i++ ) { ott[ i + 1 ] = INT_MAX; c = Stot[ i ]; // Costo indotto dal blocco di compiti da j a i inclusi. tempi = 0; // Tempi complessivi del blocco di compiti da j a i inclusi. for( j = i; j >= 0; j-- ) { c += ( tempi + S ) * costo[ j ]; tempi += tempo[ j ]; if ( c >= ott[ i + 1 ] ) break; // È inutile continuare se il // blocco costa più dell'ottimo. if ( c + ott[ j ] < ott[ i + 1 ] ) ott[ i + 1 ] = c + ott[ j ]; } } /* Completiamo il calcolo aggiungendo i costi fissi. */ tempi = 0; t = ott[ N ]; for( i = 0; i < N; i++ ) { tempi += tempo[ i ]; t += tempi * costo[ i ]; } cout << t << endl; return 0; }