Pagini recente » Cod sursa (job #2405196) | Cod sursa (job #2298683) | Cod sursa (job #2084780) | Cod sursa (job #2195525) | Cod sursa (job #2749130)
#include <fstream>
using namespace std;
int v[100010];
int n, sol, i;
int greedy(int st, int dr) {
/// determin suma maxima alegnd cate doua valori vecine din secventa cu indici
/// de la st la dr inclusiv
int rez = 0;
int f[100010] = {0};
for (int i=1;i<=n;i++)
f[i] = 0; /// niciun element din v nu a fost ales;
for (;;) {
/// caut in v 2 elemente vecine care pot fi alese si iau perechea cu
/// suma maxima dintre cele cu aceasta proprietate (conform alg greedy hotarat)
int maxim = -1, poz;
for (int i=st;i<dr;i++)
if (f[i] == 0 && f[i+1] == 0 && v[i] + v[i+1] > maxim) {
maxim = v[i] + v[i+1];
poz = i;
}
if (maxim != -1) {
rez += maxim;
f[poz] = 1;
f[poz+1] = 1;
f[poz-1] = 1;
f[poz+2] = 1; /// elementele de pe aceste pozitii le marchez ca nu mai pot
/// fi alese
} else
break;
}
return rez;
}
int main () {
ifstream fin ("oo.in");
ofstream fout("oo.out");
fin>>n;
for (i=1;i<=n;i++) {
fin>>v[i];
}
/**
Cazul 1 nu aleg pe primul
Am un sir care nu e circular cu pozitii de la 2 la n si trebuie sa aleg perechi
de cate 2
**/
/**
Cazul 2 nu aleg pe ultimul
Am un sir care nu e circular cu pozitii de la 1 la n-1 si trebuie sa aleg perechi
de cate 2
**/
/**
Cazul 3 aleg pe primul si pe ultimul
Am un sir care nu e circular cu pozitii de la 3 la n-2 si trebuie sa aleg perechi
de cate 2
**/
sol = greedy(2, n);
sol = max(sol, greedy(1, n-1));
sol = max(sol, greedy(3, n-2) + v[1] + v[n]);
fout<<sol;
return 0;
}