Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 902 byte
#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;
}
