Национална олимпиада по информатика 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
|