Pagini recente » Cod sursa (job #184869) | Cod sursa (job #1639552) | Istoria paginii runda/ada34/clasament | Cod sursa (job #1720447) | Cod sursa (job #3160764)
#include <fstream>
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
// 1 < G < 1001
// 1 < W < 5001
// 0 ≤ EGi,CGi < 10001
const int MAX_GEN = 1001;
const int INF = -1;
struct t_gen {
int energie;
int cost;
};
int dp_cost(int idx, int energie, t_gen gens[], int memo[]) {
if (energie == 0) {
return 0;
}
if (idx == 0) {
return INF;
}
if (memo[idx] != 0) {
return memo[idx];
}
// cazul 1
int cost_prev1 = dp_cost(idx - 1, energie, gens, memo);
int cost1 = cost_prev1;
// cazul 2
int cost_prev2 = dp_cost(idx - 1, energie - gens[idx].energie, gens, memo);
int cost2 = cost_prev2 + gens[idx].cost;
if (cost_prev1 == INF && cost_prev2 == INF) {
memo[idx] = INF;
return memo[idx];
}
if (cost_prev1 == INF && cost_prev2 != INF) {
memo[idx] = cost2;
return memo[idx];
}
if (cost_prev1 != INF && cost_prev2 == INF) {
memo[idx] = cost1;
return memo[idx];
}
memo[idx] = min(cost1, cost2);
return memo[idx];
}
int main() {
int nr_gen;
int cant_energ;
t_gen gens[MAX_GEN + 1];
int memo[MAX_GEN + 1] = {0};
fin >> nr_gen >> cant_energ;
for (int i = 1; i <= nr_gen; i++) {
int energie;
int cost;
fin >> energie >> cost;
t_gen energ_cost = {energie, cost};
gens[i] = energ_cost;
}
fout << dp_cost(nr_gen, cant_energ, gens, memo) << endl;
return 0;
}