Pagini recente » Cod sursa (job #2786686) | Cod sursa (job #576286) | Cod sursa (job #77577) | Cod sursa (job #450902) | Cod sursa (job #36316)
Cod sursa(job #36316)
/*
GREEDY
Time Complexity: O(N^2)
*/
#include <stdio.h>
#include <string.h>
#define filein "oo.in"
#define fileout "oo.out"
#define maxn 10000
int oo[maxn], blocked[maxn];
int main()
{
int i, j, k, N, sw;
long int max, best;
freopen(filein, "r", stdin);
scanf("%d", &N);
for (i = 0; i < N; i++)
scanf("%d", &oo[i]);
memset(blocked, 0, sizeof(blocked));
sw = 1, max = 0;
while (sw)
{
for (sw = best = i = 0; i < N; i++)
if (!blocked[i] && !blocked[(i+1)%N] && oo[i]+oo[(i+1)%N] > best)
best = oo[i]+oo[(i+1)%N], j = i, sw = 1;
if (sw)
blocked[j] = blocked[(j+1)%N] = blocked[(j+2)%N] = blocked[(j-1+N)%N] = 1,
max += best;
}
freopen(fileout, "w", stdout);
printf("%ld\n", max);
return 0;
}