Cod sursa(job #1408487)

Utilizator hopingsteamMatraguna Mihai-Alexandru hopingsteam Data 30 martie 2015 01:47:55
Problema Energii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include    <iostream>
#include    <fstream>

using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");

const int LIM = 1005;
const int EnLIM = 5005;
const int oo = (1 << 30);
int G, W;
int EG[LIM], CG[LIM];
int DP[LIM][EnLIM];

void Read()
{
    fin >> G >> W;
    for(int i = 0; i < G; i++)
        fin >> EG[i] >> CG[i];

    /*
        Programare dinamica:
            > DP[i][j] cu semnificatia: "costul minim folosind primele i generatoare cu energia j"
    */

    for(int i = 0; i < G; i++)
        for(int j = 0; j < W; j++)
            DP[i][j] = oo;

    int tEnergy;
    for(int i = 0; i < G; i++)
    {
        tEnergy += EG[i];
        for(int j = 1; j <= tEnergy && j <= W; j++)
        {
            if(EG[i] <= j)
                DP[i][j] = min( DP[i-1][j], //Nu alegem generatorul
                                DP[i-1][j - EG[i]] + CG[i]  ); //Alegem generatorul curent
            else //Cazul #GSM
                DP[i][j] = min( DP[i-1][j],
                                CG[i]   );
        }
    }

    fout << DP[G][W] << "\n";
}

int main()
{
    Read();
    return 0;
}

/*
Cazul GSM (Generator Smecher):
    -   in cazul in care exista un generator care produce
        mai multa energie cu un cost mai mic decat toate de pana acum, il alegem
*/