algoprog.kz

My DP

i = 1 .. n

j = 1 .. w

d[i][j] = max(d[i][j - 1] , d[i - 1][j] , d[i][j - a[i].w] + a[i].p , d[i - 1][j - a[i].w] + a[i].p);

Ета задача решается фибоначчи!!!динамикой у нас есть массив a[10000]={0} пока равен 0. первый элемент и второй массива будет равен 2. и циклом от 3 до N будем вычисляя,заполнять массив a[i]=a[i-1]+a[i-2]. в конце выведем a[n];

Для решения этой задачи применим метод динамического программирования. Пусть b[d][k] – количество номеров, набираемых ходом коня, которые начинаются с цифры d и состоят из k цифр. Тогда b[d][1]=1 для всех d, а b[d][k] для любого d вычисляется через сумму b[i][k-1] для k>1. Так, например, b[4][k] = b[0][k-1]+b[3][k-1]+b[9][k-1]. Увеличивая k от 2 до n мы получим значения b[d][n], сумма которых (за вычетом b[0][n] и b[8][n]) и даст ответ на поставленную задачу. Заметим также, что при вычислении могут получаться достаточно большие значения, поэтому следует применить длинную арифметику.

Основной факт заключается в том, что модуль по которому нужно брать ответ для задачи - простое число (10^9 + 7). Думаю без этого факта задачу невозможно было бы решить за полиномиальное время. Зная применение малой теоремы Ферма можно спокойно решить задачу обычной динамикой.

А именно: чтобы вычислить значение (A/B)%C, воспользуемся фактом что B^(C - 1)%C = 1, (по малой теореме Ферма, C - простой модуль). (A/B)%C == ( (A * B^(C - 2)) / (B^(C - 1)) )%C . B^(C - 1) мы можем убрать из знаменателя, так как он сравним с единицей по модулю С. Отсюда (A/B)%C = (A * B^(C - 2))%C.

Идея динамики заключается в следующем: d[i, j] = кол-во палиндромов длины i, используя первые j символов алфавита из заданной строки.

Теперь о том как считать динамику. Перебираем j Для некоторого j перебираем длину строки (i) которую мы будем апдейтить. Перебираем кол-во символов j которые мы добавим в строку (k). k от 0 до кол-во j в изначальной строке. d[i + k, j] = d[i, j] * (k!)^(C - 2) * (i+k)! * (i!)^(C - 2); Если i%2 == 0 и кол-во символов j в изначальной строке > 0 (значит можно добавить текущий символ в центр строки) d[i + 1, j] = d[i, j]; Ответом на задачу будет d[n, 26] На заметку: все вычисления нужно делать по модулю C.

В каждом следующем слое (считая сверху вниз) кубиков больше, чем в предыдущем, а в сумме их n. Значит, нам требуется представить n в виде суммы возрастающих натуральных слагаемых.

начинать мы можем со всех цифр кроме 0 и 8 значит из 8 цифр. Из каждой цифры ходом коня есть только 2 хода.

А значит ответ длинное число 8 * 2 * 2 * 2 * 2...(цифра 2 n-1 раз)

.

N = 90 - int64. Пусть F(i) - это кол-во всех способов правильно представить флаг из i полосок. На нас наложено два ограничения: - 1. Никакие два цвета не могут идти друг за другом, если они одинаковы - 2. Если сущ синий цвет, он должен стоять между белым и красном либо наоборот.

Тогда получается что количество способов для первого условия F(i-1). А так как синий не может стоять ни вначале ни в конце, то таких способов F(i-2). Значит F(i) = F(i-1) + F(i-2) - Граничные значения: F(1) = 2 (K, B), F(2) = (KB, BK)

This problem is typical knapsack but with a little spice inside.

First of all , let assume F(n,l) - the minimal amount of money needed to buy n-meters material if some amount of material was bought in l-th shop. Then it means , that you can buy in l-th shop 0-meters of material and 0-meters in l-1 shops or 1-meter of material and 0-meters in l-1 shops and so on. By this way we can easily say that : F(n, l) is min(k is [1...r]) (f(n, k) + F(n-1, r-k));

if you sure that your task is solved try this test 2 70 7 50 1 100 7 8 6 10 Complexity: O(n*(l+p)^2) and after that you can be sure! thanks in advance

Эта задача тривиальна! Так как в (i, j) клетку мы можем попасть из (i-1, j) или (i, j-1), тогда f(i,j) = min(f(i-1,j), f(i,j-1)) + k[i][j], где k[i][j] - это стоимость самой клетки. За начальные условия можно взять f[0][0] = k[0][0]; for(int i = 1; i<n; i++) f[i][0] = k[i][0] + f[i-1][0]; for(int i = 1; i<m; i++) f[0][i] = k[0][i] + f[0][i-1];

Задача решается за (O(n^2)). Подумайте как можно сделать O(n) по памяти

Пуст f[i] хранит кол-во k-based чисел длины i. В таком случае можно сделать реккурентную формулу f[i] = (k - 1)f[i - 1] + (k - 1)f[i - 2] = (k - 1)*(f[i - 1] + f[i - 2]). Т.е. мы можем просто любую цифру от 1 до к - 1 к k-based числам длины i-1, а также можем дописать 0 и любую цифру от 1 до к - 1 к k-based числам длины i-2. Так что ответом будет f[n].

Найдем все возможные кол-ва палочек которые образуют проигрышный для игрока стол. Можно делать так: один параметр - кол-во текущих палочек, далее пробуем взять какое-то кол-во палочек после этого мы попадаем в какое-то состояние если оно проигрышное значит текущее выигрышное, результат запоминаем. Далее сделаем простой рюкзак по этим кол-вам (проигрышным от 1 до n - 1). Если достигли n, и при этом кол-во использованных столов > 1. Тогда восстанавливаем ответ.

Нам надо знать какое минимальное кол-во символов может принимать длина новой строки и её саму. Для этого для каждого подотрезка будем вычеслять эти данные. При этом сначала для каждого подотрезка проверяем можем ли мы его разбить на одинаковые подподотрезки (КМП например). После чего используем ленивую динамику. А именно пытаемся разбить текущий отрезок в какой-то точке на два и посмотрим длины для обеих частей, и из всех таких разбиений выберем наименьшее по длине. Как восстановить ответ додумайте сами.

Задача на динамику. Заведем два массива. В одном будем хранить количество последовательностей расположения полосок на флаге, в которых последний цвет будет белый, а в другом красный (для синего не заводим так как последняя, да и первая полоски флага не могут быть синего цвета :) ). Теперь если мы хотим добавить еще один цвет к этой последовательности, то нам необходимо лишь знать количество последовательностей длины на единицу меньше и которые оканчиваются на другой цвет (т.к. два цвета не могут идти вподряд!) и количество последовательностей длины на 2 единицы меньше (тоже другого цвета, для того чтобы между ними вставить полоску синего цвета!). Теперь подсчитав эти два массива мы уже будем знать ответ на задачу :)

Из условия понятно, что задача сводится к проверке пересечения выпуклого многоугольника построенного из станций метро и самих шоссе, которые являются прямыми. Теперь, что нам нужно сделать так это построить эту оболочку, далее научиться проверять за быстро). Это можно сделать тернарным поиском: разобьем многоугольник на две полудуги. Для каждой полудуги будем пускать тернарный на расстояние от точки до прямой учитывая знак расстояния (мин. и макс.). Понятно, что функция расстояния будет монотонна в двух местах. Теперь сравним знаки минимумов и максимумов которые мы нашли. Если есть различные знаки или же нуль, тогда есть пересечение, в противном случае нет.