Programozás‎ > ‎Feladatok‎ > ‎Fazekas‎ > ‎Megoldás‎ > ‎

mb_fazekas.c

Letöltés: mb_fazekas.c

#include <stdio.h>
#include <string.h>

int cache[10000];
int choice[10000];
int f[10000];
int n;
int k;

int best(int index)
{
int min = -1, ido, max = 0, x, i;

if (index >= n)
return 0;

x = index + k;
if (x > n)
x = n;

for (i = index; i < x; i++) {
if (max < f[i])
max = f[i];

ido = max + cache[i + 1];

if (ido < min || min == -1) {
min = ido;
choice[index] = i;
}
}

cache[index] = min;

return min;
}

int main(int argc, char **argv)
{
int i;

memset(cache, 0, 10000 * sizeof(int));

if (scanf("%d %d", &n, &k) != 2) {
printf("Keves parameter\n");
return 1;
}

for (i = 0; i < n; i++)
if (!scanf("%d", &f[i])) {
printf("Keves paramter\n");
return 1;
}

for (i = n - 1; i > 0; i--)
best(i);

printf("%d\n", best(0));

i = 0;
while (i < n && choice[i] < n) {
printf("%d %d\n", i + 1, choice[i] + 1);

i = choice[i] + 1;
}

return 0;
}
ċ
mb_fazekas.c
(1k)
Gábor Fehér,
2012. márc. 4. 8:36
v.1
Comments