Поначалу каждый из нас выложит разбор своих задач. После соберем их в один пост.
C. Очереди к умывальникам
Задача решалась с помощью динамического программирования.
Рассмотрим такую динамику: d[i][j][k].
i --- количестов еще не обработанных человек,
j --- количестов еще не обработанных комнат,
k --- максимальная очередь в предведущих комнатах.
Наш ответ находиться в состоянии d[n][m][0]. Так же, когда j равно 1, ответ равен максимуму из очереди в последней комнате и наибольшей очереди из предведущих.
Теперь рассмотрим какое-то промежуточное состояние.
Переберем количество человек, которое пойдет в j-ю комнату. Пусть из i человек пойдет c. Тогда вероятность такого перехода состоит из 2-х сомножителей:
Cci --- какие именно студенты пойдут в j-ю комнату.
(1 / j)c· ((j - 1) / j)i - c --- вероятность того, что c студентов пойдут в j-ю комнату, а остальные в комнаты с 1-й по (j - 1)-ю.
Сумма по всем с от 0 до i значений вида
(1 / j)c· ((j - 1) / j)i - c· Cci· d[i - c][j - 1][mx] и даст ответ. Не забудте пересчитать максимум и тогда задача пройдет.
Спасибо за участие. Удачи на дорешивании и на предстоящих соревнованиях. Ведь без неё никуда.
С уважением, Иван.
1)Сначала n/2 грузовиков 1 1 0 1(один человек, один профит и один человек ниже)
2)Потом n/2 грузовиков 1 1 1 0(один человек, один профит и один человек выше)
Получается О(n^2) переходов.
Я решал D(и дорешал после контеста), хэшируя пару (l[i]+c[i]) и (r[i]) и для j-того грузовика искал хэш пары(l[j],r[j]+c[j]). Так как для грузовика есть только одна конфигурация((l[i]+c[i]) и (r[i])), после которой он может стать, то для вычисления f[j] необходимо находить только одно значение из хэш-таблицы.
А можно более подробно? Как учитывается позиция грузовика?
Что-то у меня не получается завалить свое решение подобным образом. Может алгоритм неправильный? Алгоритм такой:
1) В ответе у всех грузовиков значение l[i] + r[i] + c[i] будет одинаково(и равно общему числу людей во всех грузовиках), поэтому все грузовики можно поделить на классы эквивалентности и решать задачу для каждого класса отдельно.
2) Будем идти по грузовикам в том порядке, в котором они даны во входном файле и хранить массив dp[], где dp[i] - это максимальный профит если в первых нескольких грузовиках сидит i человек. Изначально dp[0] = 0, все остальные -inf.
3) Переходы не особо хитрые : dp[ l[i] + c[i] ] = max( dp[ l[i] + c[i] ],dp[ l[i]] + v[i] ). В конце ответ должен лежать в dp[ l[i] + r[i] + c[i] ] (i - любой грузовик из нашего класса).
When considering room j with c students inside it, the largest queue in this room is (c + basin[j] - 1) / basin[j]. Then mx is actually the greater of this value and k (hence the 'update').
class Program
{
static long[,] Cnm;
static int[] a;
static void Main(string[] args)
{
string[] s = Console.ReadLine().Split(' ');
int n = int.Parse(s[0]);
int m = int.Parse(s[1]);
a = new int[m];
string[] ss = Console.ReadLine().Split(' ');
for (int i = 0; i < m; i++)
a[i] = int.Parse(ss[i]);
BuildCnm(n);
double[, ,] d = new double[n + 1, m + 1, n + 1];
for (int L = 0; L <= n; L++)
d[0, 0, L] = L;
for (int i = 0; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
for (int L = 0; L <= n; L++)
{
for (int k = 0; k <= i; k++)
{
double prob = Cnm[i, k] * Math.Pow(1.0 / j, k) * Math.Pow(1 - 1.0 / j, i - k);
d[i, j, L] += prob * d[i - k, j - 1, Math.Max(L, (k + a[j - 1] - 1) / a[j - 1])];
}
}
}
}
Console.WriteLine(d[n, m, 0]);
}
private static void BuildCnm(int n)
{
Cnm = new long[n + 1, n + 1];
for (int i = 0; i <= n; i++)
{
Cnm[i, 0] = 1;
for (int j = 1; j <= i; j++)
Cnm[i, j] = Cnm[i - 1, j] + Cnm[i - 1, j - 1];
}
}