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


Национална олимпиада по информатика 2004, Задача 2.2. КАРТИНИ

Уловието на задачата може да прочетете тук.

Решение

Първо ще се опитаме да решим по-простата задачата без да въртим картините. Нека дефинираме функция f(n), която ни дава минималната височина за нареждането на първите n картини. Ако сложим на най-горния ред последните x картини, височината ще бъде сумата от най-високата от последните x картини и f(n-x). Така ако пробваме за всяко x, за което последните x картини се събират на един ред и вземем най-малката от горната сума, ще намерим минималната височина за първите n картини. След като сме дефинирали рекурентна зависимост за f(n), може да използваме метода на динамичното оптимиране и да изчислим функцията f(n) за всяко n. Сложността на алгоритъма ще получим като забележим, че за всяко n изпълняваме най-много по n итерации за x. Следователно сложността на алгоритъма е O(n2).

Да решим задачата когато може да въртим картините няма да се различава много от гореописаната задача. Когато изчисляваме f(n) за конкретно n и пробваме за x = 1, 2... винаги ще слагаме картините да лежат на по-дългата им страна, тоест ще се опитваме да запазим минимална височина. В един момент сумата от по-дългите страни на картините ще стане по-голяма от дължината на реда, тоест те няма да могат да се съберат на един ред ориентирани така. Тогава ние трябва да обърнем една от картините и това трябва да бъде картината с най-малка по-дълга страна. Така височината на реда ще нарасне най-малко. Ще обръщаме картини по описания начин докато всичките x картини успеят да се съберат на реда. Така намираме решението за поредното x, след което се опитваме да прибавим и следващата картина. В един момент няма да има картина, която да завъртим, тогава просто спираме и взимаме това x за което сумата от височината на най-високата картина и f(n-x) е най-малка. Как ще намираме картината с най-малка по-дълга страна. Всички картини от поредния ред ще прибавяме в една структура и всеки път когато трябва да завъртим някоя картина, ще я търсим в структурата и ще я вадим от нея. Най-подходящата структура, която да може да прибавя и изважда картина, както и да намира картината с най-малка по-дълга страна е приоритетна опашка реализирана с пирамида (heap). Тя ни дава сложност на операциите O(lgN). Както и по-горе, изчислявайки f(n), за всяко n имаме по n итерации за x и като добавим сложността от приоритетната опашка, получаваме обща сложност на алгоритъма O(N2lgN).

Примерна реализация

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;


const int maxn = 1501;


struct Pict
{
	double x, y;
};


int n;
double w;
Pict ps[maxn];
double f[maxn];


struct Cmp
{
	bool operator()(const int &x, const int &y)
	{
		return ps[x].y > ps[y].y;
	}
};


void solve();


int main()
{
	solve();

	return 0;
}

void solve()
{
	int i, j, x;
	double s, h;

	void readf();

	readf();

	f[0] = 0;
	for (i = 1; i <= n; i++)
	{
		priority_queue<int, vector<int>, Cmp> q;
		s = h = 0;
		f[i] = -1;
		for (j = i; j > 0; j--)
		{
			q.push(j);
			s += ps[j].y;
			h = max(h, ps[j].x);
			while (s > w && !q.empty())
			{
				x = q.top();
				q.pop();
				s += ps[x].x - ps[x].y;
				h = max(h, ps[x].y);
			}
			if (s <= w && (f[i] == -1 || f[j-1] + h < f[i]))
				f[i] = f[j-1] + h;
		}
	}

	printf("%f\n", f[n]);
}

void readf()
{
	double x, y;
	int i;

	scanf("%d%lf", &n, &w);

	for (i = 1; i <= n; i++)
	{
		scanf("%lf%lf", &x, &y);

		if (x > y)
			swap(x, y);

		ps[i].x = x;
		ps[i].y = y;
	}
}

			

Автор: Иван Анев


обратно към брой 27