|
розбір задачі lamps3.
нехай a[i] -- мінімальні кількість ламп, що знадобляться при R = i, а b[i]
-- номер однієї з цих ламп.
нехай що a[0] = 0,b[0] = 0. та для всіх відємних і a[i] = 0.
тоді a[i] = min(a[i-r[1]],a[i-r[2]],...,a[i-r[N]]);(пробуємо ставити всі лампи).
а b[i] -- номер j тієї лампи, що в a[i-r[j]] і є мінімальним значенням при
вирахуванні a[i].
отже звідси ми можемо знайти a[1],a[2],...a[R].
за допомогою масиву b легко знайти самі лампи.
та годі вже пояснювати! ось програма!
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define uchar unsigned char
#define MAXS 25000
int main(void)
{
long n, s, i, j, tmp;
long r[15];
long a[MAXS + 1];
long b[MAXS + 1];
uchar z[16];
long FORLIM, FORLIM1;
scanf("%ld", &s);
scanf("%ld", &n);
FORLIM = n;
for (i = 1; i <= FORLIM; i++)
scanf("%ld", &r[i-1]);
FORLIM = s;
for (i = 1; i <= FORLIM; i++) {
a[i] = 32000;
FORLIM1 = n;
for (j = 1; j <= FORLIM1; j++) {
if (i - r[j-1] >= 0 && a[i - r[j-1]] + 1 < a[i]) {
a[i] = a[i - r[j-1]] + 1;
b[i] = j;
}
}
}
tmp = s;
while (tmp != 0) {
z[b[tmp]]++;
tmp -= r[b[tmp] - 1];
}
printf("%ld", a[s]);
FORLIM = n;
for (i = 1; i <= FORLIM; i++)
printf(" %d", z[i]);
printf("\n");
return 0;
}
|
|
