Динамическое программирование

Решение задачи методом динамического программирования как правило требует наличия рекуррентного соотношения между подзадачами. Скорость решения задач этим методом как правило полиномиальна, в отличии от методов полного перебора или бектрекинга.

Пример входа	Пример выхода
4 9	21
2 5
2 5
4 9
1 2

Пример входа	Пример выхода
0.20	0.20 4
2.00	2.00 293
0.00

Рассмотрим пример. Пусть имеются три матрицы со следующими размерами: X – 5  10, Y – 10  20, Z – 20  35.

• 
  XY: 5 * 10 * 20 = 1000 операций, получим при этом матрицу размера 5  20;
  
• 
  ((X Y) Z): 5 * 20 * 35 = 3500 операций;
  
• 
  Общее число умножений равно 4500.
  

• 
  YZ: 10 * 20 * 35 = 7000 операций, получим при этом матрицу размера 10  35;
  
• 
  (X (YZ)): 5 * 10 * 35 = 1750 операций;
  
• 
  Общее число умножений равно 8750.
  

Пример входа	Пример выхода
3	Case 1: (A1 x (A2 x A3))
1 5	Case 2: ((A1 x A2) x A3)
5 20	Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
20 1
3
5 10
10 20
20 35
6
30 35
35 15
15 5
5 10
10 20
20 25
0

Пример входа	Пример выхода
a1b2c3d4e	4
zz1yy2xx3ww4vv	3
abcdgh	26
aedfhr	14
abcdefghijklmnopqrstuvwxyz
a0b0c0d0e0f0g0h0i0j0k0l0m0n0o0p0q0r0s0t0u0v0w0x0y0z0
abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn

Пример входа	Пример выхода
3 2	Yes, Teobaldo can travel.
1 2	No, Teobaldo can not travel.
2 3
3 1 2
3 2
1 2
1 3
1 3 2
0 0

Пример входа	Пример выхода
3 1 2 2	7
0 3 5
5 0 1
9 2 0
2 3
0 0 0 0

Пусть M₀ – максимально допустимая скорость трамвая, с которой он может выехать с начальной станции P₀. Тогда максимальная скорость, с которой трамвай может выехать со станции P_i-1, равна M_i = M₀ – C_i, где C_i – суммарное количество поломок на промежутках S₁, …, S_i-1.

Вычисление среднего времени покажем на примере. Пусть длина пути равна 300 метров, максимально возможная начальная скорость равна 25 метров в секунду. Если водитель выберет скорость 25 м/с, то трамвай обязательно поломается. И тогда он проедет половину пути за 150 / 25 = 6 секунд, простоит 10 секунд и доедет с аварийной скоростью 5 м/с до следующей остановки за 150 / 5 = 30 секунд. Всего при этом потратив 6 + 10 + 30 = 46 секунд. Допустим, что водитель выбирает скорость 15 метров в секунду. С вероятностью 15 / 25 = 0.6 произойдет поломка. В случае поломки трамвай проедет 150 метров со скоростью 15 м/с (потратив на это 10 секунд), потом 10 секунд простоит и со скоростью 5 м/с доедет до конца (150 / 5 = 30 секунд). С вероятностью 0.4 трамвай не поломается и доедет до следующей остановки за 300 / 15 = 20 секунд. Средний час равен 0.6 * 50 + 0.4 * 20 = 38 секунд.

В задаче необходимо вычислить наименьшее среднее время, за которое трамвай может проехать весь путь от остановки P₀ до P_n.

Пример входа	Пример выхода
25 1 900	102.0000
25 2 900 900	205.0303
25 2 305.15 980.76	150.0000
5 1 1000	210.0000

	Предмет 1	Предмет 2	Предмет 3
1	14	10	10
2	13	11	10
3	13	10	11
4	12	11	11
5	12	10	12
6	11	11	12
7	11	10	13
8	10	11	13
9	10	10	14
10	11	12	11
11	10	12	12
12	12	12	10
13	10	13	11
14	11	13	10
15	10	14	10

Пример входа	Пример выхода
2	15
3 34 10	15
3 34 10

Пример входа	Пример выхода
20 2	21
20 2	21
0 0

Похожестью группирующей системы называется число, равное сумме произведений всех элементов групп, взятой по модулю m. Похожесть для представленного выше примера для k = 1 равна F₁ = (a + b + c + d) mod m. Для k = 2 похожесть равна F₂ = (ab + ac + ad + bc + bd + cd) mod m.

Для заданного множества чисел и среди всех всевозможных k = 1, …, n найти похожесть F_k с максимальным значением.

Вход. Первая строка каждого теста содержит числа n (2  n  1000) и m (1  m  2³¹). Следующая строка содержит n положительных целых чисел. Все числа не более 1000. Последний тест содержит n = m = 0 и не обрабатывается.

Выход. Для каждого теста вывести значение максимальной похожести среди всех возможных групп.

Пример входа	Пример выхода
4 10	5
1 2 3 4	50
4 100	5
1 2 3 4
4 6
1 2 3 4
0 0

Класс: CountingCommonSubsequences

Метод: long long countCommonSubsequences(String a,

String b, String c)

Ограничения: a, b и c содержат от 1 до 50 символов ‘a’ – ‘z’.

Вход. Три строки a, b и c.

Выход. Количество общих подпоследовательностей трех строк a, b и c.

Пример входа

a	b	c
“call”	“accelerate”	“candle”
“topcoder”	“topcoder”	“topcoder”
“no”	“correct”	“answer”

6

239

1. Пустая строка является правильной.

2. Если строка s правильная, то правильными являются также (s), [s] и {s}.

3. Если строки s и t правильные, то правильной будет строка st.

Например, строки “([{}])”,“” и “(){}[]” являются правильными, а “([}]”,“([)]” и “{” – нет.

Класс: CorrectingParenthesization

Метод: int getMinErrors(string s)

Ограничения: s содержит от 0 до 50 символов, s содержит четное количество символов ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’.

s

"([{}])()[]{}"

"([)]"

"([{}[]"

0

2

Класс: SumThemAll

Метод: long long getSum(int lowerBound, int upperBound)

Ограничения: 0  upperBound  2*10⁹, 0  lowerBound  upperBound.

lowerBound	upperBound
0	3
14	53
24660	308357171

6

296

Необходимо найти максимальную площадь участка, которую можно оградить треугольными формами.

Класс: GrasslandFencer

Метод: double maximalFencedArea(vector fences)

Ограничения: fences содержит от 1 до 16 элементов, 1  fences [i]  100.

Вход. Целочисленный массив fences, содержащий длины имеющихся кусков забора.

Выход. Максимальная площадь, которую можно оградить треугольными формами.

Пример входа

fences

{3,4,5,6,7,8,9}

{1,2,4,8}

{7,4,4,4}

36.754383146489694

0.0

6.928203230275509

Класс: FenceRepairing

Метод: double calculateCost(vector boards)

Ограничения: boards содержит от 1 до 50 элементов, boards[i] содержит от 1 до 50 символов ‘.’ И ‘X’.

boards

{"X.X...X.X"}

{"X.X.....X"}

{".X.......X", "..........", "...X......", "...X..X...", "..........", "..........", "..X....XX.", ".........X", "XXX", ".XXX.....X"}

3.0

9.591663046625438

По заданным числам a, b и k следует найти счастье каждого числа между a и b включительно по отношению к k и вернуть их сумму.

Класс: ExtendedHappyNumbers

Метод: long long calcTheSum(int a, int b, int k)

Ограничения: 1  a, b  10⁶, 1  k  6.

Вход. Три числа a, b, k.

Выход. Найти счастье каждого числа между a и b включительно по отношению к k и вернуть их сумму.

Пример входа

a	b	k
13	13	2
1	5	2
535	538	3

1

14

Класс: FastPostman

Метод: int minTime(vector address, vector maxTime,

int initialPos)

Ограничения: address и maxTime содержат одинаковое количество элементов, не большее 50, 1  address[i], initialPos  10⁶, 1  maxTime[i]  10⁹, 1  maxTime[i]  10⁹.

Вход. Массив адресов домов address и массив maxTime, содержащий граничное время разноса соответствующих писем. Переменная initialPos содержит начальное положение почтальона.

Выход. Наименьшее время, за которое почтальон сможет разнести все письма по указанным адресам с учетом граничного времени. Если он не сможет это сделать, то вернуть -1.

Пример входа

address	maxTime	initialPos
{1,3,5,7}	{9,2,5,100}	4
{1,5}	{6,2}	3
{1000000,1000000,1000000,1000000}	{563,23452,32426,1}	1000000
{1000000}	{45634}	876

13

6

-1
19. Прыгатель по платформам [Топкодер, раунд 353, дивизион 2, уровень 3; дивизион 1, уровень 2]. В старой аркадной игре Вы попали на бонусный уровень. Имеется набор платформ, на которых находятся монеты. Вы должны прыгать с одной платформы на другую, собирая деньги. С каждой платформы можно прыгать только на платформу, находящуюся ниже. Начальной можно выбрать любую платформу.

Опишем поведение игрока при прыжках. При каждом прыжке горизонтальная составляющая скорости является константой, не превышающей v. Движение вниз происходит по законам физики: ускорение свободного падения равно g. Начальная скорость игрока равна 0.

Каждая платформа является точкой и имеет формат “X Y C”, где X и Y – координаты платформы, а C – количество монет на ней. Большие значения координаты Y имеют платформы, находящиеся выше. Определить наибольшее количество монет, которое может собрать игрок.

Класс: PlatformJumper

Метод: int maxCoins(vector platforms, int v, int g)

Ограничения: platforms содержит от 1 до 50 элементов, platforms[i] имеет формат “X Y C”, 0  X, Y  5000, 0  C  10000, 1  g, v  100.

Вход. Информация о платформах platforms, наибольшая возможная горизонтальная составляющая скорости игрока v и ускорение свободного падения g.

Выход. Наибольшее количество монет, которое может собрать игрок.

Пример входа

platforms	v	g
{"3 10 7", "5 15 7", "8 9 12" }	2	10
{"0 0 1", "2 4 1", "4 0 1"}	1	2
{"0 0 1", "5000 5000 10"}	100	87

14

2

f(i + 1) = f(i + 1 – v_j) + 1, i + 1  v_j

По умолчанию положим f(0) = 0, так как сумму в 0 копеек можно выдать 0 монетами. Значения решений для подзадач f(i) храним в некотором числовом массиве m.

Пример. Пусть имеются монеты достоинством 1, 2 и 5 копеек. Значение искомой суммы равно S = 9. Значение элементов массива m имеет вид:

i	0	1	2	3	4	5	6	7	8	9
f(i)	0	1	1	2	2	1	2	2	3	3

f(i, w) = max( f(i – 1, w), f(i – 1, w - w_i) + c_i), i > 1

#include

#define MAX 10
int i,j,n,w;

int weight,cost,m[MAX];

void main(void)

{

memset(m,-1,sizeof(m));m[0] = 0;

scanf("%d %d",&n,&w);

for(i=0;i

{

scanf("%d %d",&weight,&cost);

for(j = MAX - 1; j >= weight; j--)

if ((m[j - weight] >= 0) && (m[j] < m[j - weight] + cost))

m[j] = m[j - weight] + cost;

}

printf("%d\n",m[w]);

}
3. Доллары [Вальядолид, 147, 357, 674]. Обозначим через f(k, n) количество способов составить сумму n из первых k номиналов монет. Оно равно количеству способов составить сумму n первыми (k – 1) номиналами плюс количество способов составить сумму (n – a_k) k номиналами. Имеем соотношение:

f(k, n) = f(k – 1, n) + f(k, n – a_k)

k \ n
				f[k - 1, n]
	f[k, n – ak]			f[k, n]

Изначально положим f(0, 0) = 1, f(n, 0) = 0, n > 0.

жүктеу/скачать 0.53 Mb.

Достарыңызбен бөлісу: