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; } |