Текущ брой на Списание ИнфоМан
 


НОИ 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