НОИ 2005 - 2 кръг, Задача A1. ПОДРЕДИЦИ
Условието на задачата може да прочетете
тук.
Решение
Решението на задачата се основава на метода на
динамичното оптимиране. Можем да разделим голямата задача на по-малки
поздзадачи по два параметъра. Първият параметър е каква сума искаме да получим,
а вторият – кое е най-голямото число, което можем да ползваме, за да получим
тази сума. Нека с t[last][sum]
бележим колко са вариантите да получим сума sum,
като използваме най-голямо число last.
Така например t[6][4] е равно на 1, защото ако ползваме само числата от 1 до 4
можем да получим 6 по един единствен
начин, а именно 2+4. Много лесно се
вижда следната рекурентна формула:
t[last][sum]
= t[last-1]][sum] + t[last-1][sum-last], (1)
разбира се при положение, че sum-last е положително число. Освен това
t[last][0] = 1 за всяка стойност на last, понеже сумата 0 винаги можем да получим. Рекурентната формула
(1) се обяснява комбинаторно така – ако искаме
да пресметнем вариантите, означени с
t[last][sum], то има две възможности –
да използваме числото last ( тогава
най-голямото число, което можем да ползваме, вече става last-
1, а сумата намалява с last) и да не използваме числото last, тогава сумата се запазва и отново най-голямото число,
което можем да използваме, е last-1.
Отговорът на задачата се съдържа в t[N-1][N]. Сложността на описаното
решение е O(N2), понеже ще се направят точно N*N опреации, всяка от
които изисква константно време, докато се достигне до отговора. Забележете, че
понеже винаги използваме само последните 2
реда на масива, тоест последния ред зависи само от предния, е достатъчно да съхраняваме само 2 реда от масива, а не цяла матрица N*N.
Примерна реализация:
#include <stdio.h>
#define MAX 512
__int64 row[2][MAX]; // masiv za dinamichnoto
int CUR_ROW = 1; // index na tekushtia red
int PREV_ROW = 0; // index na prednia red
int main () {
int N;
scanf("%d",&N);
row[PREV_ROW][0] = 1; // nuleva suma mojem winagi da poluchim
for (int i=1;i<N;i++) {
// i - poslednoto chislo, koeto e posledno
row[CUR_ROW][0] = 1; // nuleva suma mojem winagi da poluchim
for (int sum=1;sum<=N;sum++) {
// sumata, koiato iskame da poluchim
// vinagi e validno da ne polzwame tekushtoto chislo
row[CUR_ROW][sum] = row[PREV_ROW][sum];
if (sum-i>=0)
// izpozlwame tekushtoto chislo ako mojem
row[CUR_ROW][sum] += row[PREV_ROW][sum-i];
}
// razmeniame tekushtia i prednia red
CUR_ROW = !CUR_ROW;
PREV_ROW = !PREV_ROW;
}
printf("%I64d\n",row[PREV_ROW][N]);
return 0;
}
Автор: Слави Маринов
обратно към брой 27
|