Есть задача про Фотографа-зануду
Лично я осилил ее несколько "с фланга", а не составлением динамики, то есть сбрутфорсил полным перебором решения для размерностей до 5-6, и через известную базу данных последовательностей получил формулу (к счастью, такая последовательность там была).
Вопрос номер 1: вообще, для мира спортивного решения "канает" такое решение? Я имею ввиду использование этой базы данных для решение задач, вместо честного вывода формулы.
Вопрос номер 2: в обсуждении этой задачи на Тимусе даются две динамики, смысл которых мне не удается пока постичь.
№1
a[i][1] = a[i - 1][1] + a[i - 1][2],
a[i][2] = a[i - 1][2] + a[i - 3][2]
a[i][2] = a[i - 1][2] + a[i - 3][2]
№2
a[i][1] = a[i-1][1] + a[i-2][2]
a[i][2] = a[i-2][1] + 1
a[i][2] = a[i-2][1] + 1
Может кто-нибудь просто словами проговорить физический смысл a[i,t] в обоих случаях? Ясно, что i - это длина ряда в текущей подзадаче, а вот что такое t?
Кстати, во втором варианте видимо опечатка, должно быть a[i][1] = a[i-1][1] + a[i-1][2]
решения по поиску формулы в интернете "канают" очень часто на сборах в Петрозаводске или, например, на топкодере
на соревнованиях ACM-ICPC у тебя не будет интернета и, как следствие, вся эта база данных окажется недоступна
поэтому крайне желательно уметь всё делать самому :)
Я сдал её давным-давно, сейчас посмотрел, и там формула оказалась
a[i] = a[i-1] + a[i-3] + 1.
Только совсем не помню, как её получил =(
Как я помню, я использовал это: если на позиции i стоит студент x, то на позиции i + 1 может стоять только студент x + 1 или x + 2. Причём если мы ставим студента x + 2, то после него обязательно должен быть x + 1, иначе его некуда будет поставить.
Здесь используюется то, что нет студентов младше x. И это можно использовать, так как на первое место мы ставим самого молодого.
Если я делаю так
1 3 5 7 9 11 10 8 6 4 2
То допустим если рассмотреть позицию после тройки, я ставлю пятерку (n+2), но после этого я НЕ ставлю n+1, правильно? То есть я не обязан ставить n+1 если после n я поставил n+2.
Ну и даже в семпле, 1 3 4 2 - после единицы стоит тройка, но после тройки не стоит двойка.
Так что это рассуждение не очень верно.
1 2 3 4 6 8 10 9 7 5
То есть такая последовательность (где есть n, n+2, а затем не n+1) не одна
Или мы строим последовательность справа налево?
Вот собсна код:
d[0][0]=1;
d[1][0]=1;
for (int i=1;i<n;i++)for (int j=0;j<2;j++){
d[i+1][0]+=d[i][j];
if (!j)d[i+2][1]+=d[i][j];
}
for (int i=1;i<n;i++)ans+=d[i][0]*(n-i>2);
cout << ans+d[n][0]+d[n][1] << endl;
поясню.. так получаеться, что в какой-либо правильной посадке сначала будет i чисел, идущих "почти по возрастанию" (например 1,3,2,4,5 или 1,3,2,4,6,5), где i-ое число будет i или i-1 и разность соседних не будет превышать 2.
а потом "лесинкой" через 1 один к n и обратно(например 4,6,8,5,3 или 3,5,7,9,8,6,4)
пример("-" разделяет первую и вторую часть): 1,3,2,4,5 - 7,9,11,10,8
воот, у меня в решении динамика d[i][j] количество "почти возрастающих" перестановок длины i, в которых последнее число равно i, если j=0, или i-1, если j=1.
Вобщем я перебираю размер первой части и перемножаю количество вариантов первой части на количество второй. Первый множитель я просчитал динамикой, а второй почти всегда будет равен 1, если размер второй части достаточно большой, чтобы нарушить "почти возрастание".
Ну и остаётся учесть случаи, где какая-либо часть нулевой длины.
Вот вроде все^^