Първо Kонтролно за BOI 2004, Задача 1. ИЗКАЧВАНЕ
Уловието на задачата може да прочетете тук.
Решение
Кратък анализ на задачата показва, че от входните данни не може да се изведе
никаква подредба, която да бъде спазвана при търсене на оптимално решение.
Когато не може да наложим някаква, дори частична наредба, методът на динамичното
оптимиране, които се ползва при подобни оптимизационни задачи, почти винаги е
неприложим. Това разсъждение както и ограниченията на задачата (N <
10) ни навеждат на мисълта, че решението на задачата ще се основава на
някакъв вид изчерпване.
Нека сме определили някаква наредба на N-те алпиниста. Изчисляването
на сумарното време за изкачване ще ни отнеме O(N.M) време. Всички
възможни наредби на N алпиниста са N! на брой. Следователно общата
сложност на решение, в което ще опитаме всички възможни наредби е
O(N!.N.M). За съжаление при максимални допустими стойности на N и
M, подобно решение ще бъде по-бавно от допустимото.
За решаването на задачата ще приложим метод, при който избираме
последователно алпинистите. Генерацията на наредбите ще реализираме с рекурсия.
Когато изберем поредния алпинист, ние може да направим оценка на решението до
момента и да изчислим стойност, от която текущото решение не може да е по-малко.
Ако тази стойност е по-голяма от най-доброто решение намерено до момента, това
означава, че независимо как наредим останалите алпинисти, няма да получим
по-добро решение. По-такъв начин спестяваме проверка на някой неперспективни
наредби. Оценката на решението ще зависи от времето, за което ще мине различните
отсечки, последния поставен алпинист (неговите времена зависят от тези преди
него). Знаейки времето на последния поставен алпинист, ние знаем, че всички след
него ще бъдат поне толкова бавни. Така ако умножим броят на оставащите алпинисти
по времето за преминаване на последния поставен ще получим сумарно време, от
което решението не може да бъде по-малко.
Примерна реализация
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10;
const int maxm = 50;
int n, m, best_sum;
int a[maxn][maxm], v[maxn][maxn];
int used[maxn], best[maxn], perm[maxn];
void solve();
int main()
{
solve();
return 0;
}
void solve()
{
int i, j;
void gen(int level, int sum);
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
for (j = 0; j < m; j++)
scanf("%d", &a[i][j]);
best_sum = 1000000000;
gen(1, 0);
printf("%d\n", best_sum);
for (i = 1; i < n; i++)
printf("%d ", best[i]);
printf("%d\n", best[n]);
}
void gen(int level, int sum)
{
int i, j, t;
if (sum < best_sum)
{
if (level == n + 1)
{
best_sum = sum;
memcpy(best, perm, sizeof(best));
}
else
{
for (i = 1; i <= n; i++)
if (used[i] == 0)
{
for (j = t = 0; j < m; j++)
{
v[level][j] = max(v[level-1][j], a[i][j]);
t += v[level][j];
}
if (sum + t * (n - level + 1) < best_sum)
{
perm[level] = i;
used[i] = 1;
gen(level + 1, sum + t);
used[i] = 0;
}
}
}
}
}
Автор: Иван Анев
обратно към брой 27
|