Pagini recente » Cod sursa (job #3159233) | Cod sursa (job #1227710) | Cod sursa (job #3265766) | Cod sursa (job #128188) | Cod sursa (job #3267563)
/*
ferma este circulara, impartita in N sectoare
in fiecare sector, exista o gaina care depune un anumit numar de oua
fermierul poate aduna oua din doua sectoare adiacente in fiecare pas, dar, din cauza lacomiei,
ouale din sectoarele vecine celor doua sectoare alese nu mai pot fi adunate
scopul problemei: sa determinam numarul maxim de oua pe care fermierul le poate aduna
strategie:
1. definirea problemei
* fermierul alege doua sectoare adiacente pentru a aduna ouale, iar sectoarele vecine devin inaccesibile
* fermierul vrea sa adune ouale astfel incat sa maximizeze
2. modelarea problemei
* problema este potrivita PD
* vom defini un vector dp in care sa pastram numarul maxim de oua care pot fi adunate la fiecare pas
3. observatii
* fermierul poate incepe de la orice sector si poate aduna ouale din sectoare consecutive
* trebuie sa evitam sectoarele care sunt vecine sectoarelor selectate
4. subprobleme
* se pot lua trei posibile inpceputuri: (1, 2), (2, 3), (3, 4) etc avand in vedere ca ferma este circulara
* in fiecare caz, trebuie sa rezolvam subprobleme privind ce sectoare pot fi adunate, avand in vedere
ca sectoarele adiacente celor alese sunt inaccesibile
Algoritm si implementare
1. Citim numarul de sectoare si numarul de oua depuse de fiecare gaina in fiecare sector
2. Cream un vector dp[] pentru a salva solutiile intermediare. Acest vector va pastra pentru fiecare
sector maximul de oua care pot fi adunate pana la acel sector, respectand regulile
3. Vom defini o functie solve(start, end) care va calcula numarul maxim de oua pentru un interval
dat de sectoare, respectand regula ca sectorul ales si vecinii sai sunt inaccesibili
* aceasta functie va utiliza PD pentru a calcula valorile corecte
4. vol calcula solutia pentru fiecare posibila pereche de sectoare adiacente si vom returna maximul
*/
#include <bits/stdc++.h>
using namespace std;
ifstream in("oo.in");
ofstream out("oo.out");
int v[1000005]; // vectorul care va stoca numarul de oua din fiecare sector
int dp[1000005]; // vectorul pentru programare dinamica
int n, add; // n - numarul de sectoare; add - variabila auxiliara pentru calculul DP
int ans; // rezultatul final
int solve(int start, int end)
{
// initializam vectorul dp cu 0
for (int i = 1; i <= n + 1; i++)
dp[i] = 0;
// calculez dp pentru intervalul [start, start + end - 1]
for (int i = start + 1; i <= start + end - 1; i++) {
add = 0; // resetam varaibila add
if (i >= 4) {
add = dp[i - 3]; // daca putem aduna ouale de la acest sector, adaug valoarea
}
// maximizez valoarea dp la sectorul curent
dp[i] = max(dp[i - 1], v[i - 1] + v[i] + add);
}
// returnez rezultatul pentru intervalul [start, start + end - 1]
return dp[start + n - 2];
}
int main()
{
in >> n;
for (int i = 1; i <= n; i++)
in >> v[i];
v[n + 1] = v[1]; // ferma circulara, deci sectorul n + 1 este adiacent sectorului 1
// calculez numarul maxim de oua pentru fiecare posibila pereche de sectoare adiacente
ans = max(solve(3, n), solve(1, n));
ans = max(ans, solve(2, n));
out << ans;
return 0;
}