Национална олимпиада по информатика 2004, Задача 1.1. МИНИМУМ
Уловието на задачата може да прочетете тук.
Решение
Задачата може да се реши много лесно ако приложим метода
на грубата сила и проверим за всяка комбинация от стойности на променливите
каква ще е сумата от функциите и изберем най-малката такава. За съжаление
такова решение има сложност O(2n.m) и за n=29 и m=9 няма да се вмести във времевото
ограничение. Въпреки това решението не се отдалечава много от времевото
ограничение и ако успеем да оптимизираме елементарното решение ще постигнем
желания ефект.
Една лесна оптимизация е ако някоя променлива не участва
в нито една функция няма да я включваме в изчерпването. Въпреки това може да се
случи, че всички променливи участват в поне едно уравнение. Друга сравнително
лесна оптимизация е ако някоя променлива участва само в една функция. Тогава може да
извадим тази променлива от променливите, от които зависи функцията. Когато
извадим една променлива от множеството на променливите на функцията се променя
и множеството на стойностите на функцията. И по-точно то става два пъти
по-малко. Какви ще бъдат новите стойности, които ще заема функцията. Нека
вземем една комбинация от стойности на останалите променливи в множеството на
функцията. В предишното множество от променливи са съществували две подобни
комбинации от стойности. В едната от комбинациите отстранената променлива е
била нула, в другата единица, а всички останали променливи имат стойности като в
редуцираната комбинация (тази без отстранената променлива). Стойността, която
ще съпоставим на комбинацията от редуцираното множество ще бъде по-малката от
двете в нередуцираното множество. Логиката е, че щом
премахната променлива участва само в тази функция, за всяка комбинация от
другите променливи може да изберем стойност на отстранената променлива, която
ще даде по-малка стойност на функцията. Така съумяхме да премахнем и
променливите, които участват в само една функция.
Дали тези две оптимизации ще бъдат достатъчни. Според
условието никоя функция не зависи от повече от пет променливи. Това значи, че
имаме най-много 45 участия на променливи във функции. От друга страна за да
участва всяка от 29 променливи в поне две функции са ни нужни поне 58 участия.
Очевидно подобно нещо е невъзможно. Лесно се вижда, че в най-лошия случай ще
трябва да изчерпваме по 22 променливи, като всяка от тях участва в поне 2
функции. Което е достатъчно подобрение и ще реши задачата за отпуснатото време.
Техническата реализация на решението включва използване
на побитови операции. Стойностите които заема една функция ще бъдат съхранявани
в масив, като позиция x ще отговаря за
комбинация от стойности на променливите съответстваща на побитовото представяне
на x. По-точно ако бит i на x е 1, то
и променлива i има стойност 1.
За всяка функция също ще пазим броя на променливите, от които зависи, както и
масив от самите променливи. За променливите ще пазим в колко функции участват,
както и една от функциите в които участват. Така ако някоя променлива участва в
една функция ще знаем точно коя. В примерната реализация има две важни функции
– findmin и compress. Първата
генерира всички комбинации от стойности за променливите, които участват в поне
две функции. Втората функция премахва променлива, която участва само в една
функция, като преизчислява множеството от заеманите от функцията стойности.
Примерна реализация
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 29;
const int maxm = 9;
const int maxc = 32;
int n, m, minval;
int func_val[maxm][maxc];
int var_count[maxm];
int vars[maxm][5];
int used[maxn], by_func[maxn];
void solve();
int main()
{
solve();
return 0;
}
void solve()
{
int i, j;
int comb[maxn];
void findmin(int l, int comb[]);
void compress(int x);
scanf("%d%d", &m, &n);
for (i = 0; i < m; i++)
{
scanf("%d", var_count + i);
for (j = var_count[i] - 1; j >= 0; j--)
{
scanf("%d", vars[i] + j);
vars[i][j]--;
used[vars[i][j]]++;
by_func[vars[i][j]] = i;
}
for (j = 0; j < 1 << var_count[i]; j++)
scanf("%d", func_val[i] + j);
}
for (i = 0; i < n; i++)
if (used[i] == 1)
compress(i);
minval = 10000;
findmin(0, comb);
printf("%d\n", minval);
}
void findmin(int l, int comb[])
{
int i, j, x, val;
if (l == n)
{
val = 0;
for (i = 0; i < m; i++)
{
x = 0;
for (j = 0; j < var_count[i]; j++)
if (comb[vars[i][j]])
x += 1 << j;
val += func_val[i][x];
}
if (val < minval)
minval = val;
}
else
{
comb[l] = 0;
findmin(l + 1, comb);
if (used[l])
{
comb[l] = 1;
findmin(l + 1, comb);
}
}
}
void compress(int x)
{
int i, pos, f, mask1, mask2;
int new_val[maxc];
f = by_func[x];
for (pos = 0; vars[f][pos] != x; pos++)
;
var_count[f]--;
for (i = pos; i < var_count[f]; i++)
vars[f][i] = vars[f][i+1];
mask1 = (1 << pos) - 1;
mask2 = ~mask1;
memset(new_val, 0, sizeof(new_val));
for (i = 0; i < 1 << var_count[f]; i++)
new_val[i] = min(func_val[f][(i&mask1)|((i&mask2)<<1)|1<<pos],
func_val[f][(i&mask1)|((i&mask2)<<1)]);
memcpy(func_val[f], new_val, sizeof(new_val));
used[x] = 0;
}
Автор: Иван Анев
обратно към брой 27
|