Динамическое программирование - История изменений

Ctrlalt: /* Соответствие строки шаблону */

2023-06-18T16:43:07Z

Соответствие строки шаблону

← Предыдущая версия		Версия от 16:43, 18 июня 2023
Строка 418:		Строка 418:
	Вид ответа: d[n][m]. Сложность O(N<sup>2</sup> × M).		Вид ответа: d[n][m]. Сложность O(N<sup>2</sup> × M).

	* [~~http~~://acmp.ru/index.asp?main=task&id_task=104 ACMP #104 ~~— Шаблон~~]		* [https://acmp.ru/index.asp?main=task&id_task=104 ACMP 104]
			* [https://informatics.msk.ru/mod/statements/view.php?chapterid=3819 MCCME 3819]
			* [https://informatics.msk.ru/mod/statements/view.php?chapterid=112626 MCCME 112626]

	== Двумерная динамика (вход — две последовательности; подзадача — два префикса; модификация) ==		== Двумерная динамика (вход — две последовательности; подзадача — два префикса; модификация) ==

Ctrlalt: /* Бросание шариков */

2023-06-15T19:46:50Z

Бросание шариков

← Предыдущая версия		Версия от 19:46, 15 июня 2023
Строка 244:		Строка 244:

	* [http://brilliant.org/wiki/egg-dropping/ Brilliant.org — Egg dropping]		* [http://brilliant.org/wiki/egg-dropping/ Brilliant.org — Egg dropping]
			* [https://informatics.msk.ru/mod/statements/view.php?chapterid=3815#1 MCCME 3815]

	=== Другие задачи ===		=== Другие задачи ===

Ctrlalt: /* Наибольшая возрастающая подпоследовательность (LIS) */

2022-12-21T17:23:56Z

Наибольшая возрастающая подпоследовательность (LIS)

← Предыдущая версия		Версия от 17:23, 21 декабря 2022
Строка 137:		Строка 137:


			\|width=50%\|
			int getLisSize(vector<int> &a) {
			vector<int> lisLast(a.size() + 1, 1e9);
			lisLast[0] = -1e9;

			for (int value : a)
			*lower_bound(lisLast.begin(), lisLast.end(), value) = value;

			int lisSize = a.size();
			while (lisLast[lisSize] == 1e9)
			lisSize--;
			return lisSize;
			}
			\|-
			\|width=50%\|
	vector<int> getLis(vector<int> &a) {		vector<int> getLis(vector<int> &a) {
	vector<int> lisSize(a.size(), 1);		vector<int> lisSize(a.size(), 1);
Строка 158:		Строка 172:
	return lis;		return lis;
	}		}




	\|width=50%\|		\|width=50%\|
	int ~~getLisSize~~(vector<int> &a) {		vector<int> getLis(vector<int> &a) {
	vector<int> lisLast(a.size() + 1, 1e9);		vector<int> lisLast(a.size() + 1, 1e9);
	lisLast[0] = -1e9;		lisLast[0] = -1e9;
			vector<int> lisLastIndex(a.size() + 1, -1);
	for (int ~~value :~~ a)		vector<int> from(a.size(), -1);
	*lower_bound(lisLast.begin(), lisLast.end(), ~~value~~) = ~~value~~;
			for (int i = 0; i < a.size(); i++) {
			int lisSize = lower_bound(lisLast.begin(), lisLast.end(), a[i]) - lisLast.begin();
			lisLast[lisSize] = a[i];
			lisLastIndex[lisSize] = i;
			from[i] = lisLastIndex[lisSize - 1];
			}

	int lisSize = a.size();		int lisSize = a.size();
	while (lisLast[lisSize] == 1e9)		while (lisLast[lisSize] == 1e9)
	lisSize--;		lisSize--;
	return ~~lisSize~~;
			vector<int> lis;
			for (int i = lisLastIndex[lisSize]; i != -1; i = from[i])
			lis.push_back(a[i]);
			reverse(lis.begin(), lis.end());

			return lis;
	}		}
	\|}		\|}

Ctrlalt: /* Наибольшая возрастающая подпоследовательность (LIS) */

2022-12-14T17:39:43Z

Наибольшая возрастающая подпоследовательность (LIS)

@@ Строка 128: / Строка 128: @@
       vector<int> lisSize(a.size(), 1);
-      for (int i = 2; i < a.size(); i++)
+      for (int i = 1; i < a.size(); i++)
           for (int j = 0; j < i; j++)
               if (a[j] < a[i] && lisSize[i] < lisSize[j] + 1)
@@ Строка 136: / Строка 136: @@
+  }
 |width=50%|

Ctrlalt: /* Наибольшая возрастающая подпоследовательность (LIS) */

2022-12-12T01:09:47Z

Наибольшая возрастающая подпоследовательность (LIS)

@@ Строка 122: / Строка 122: @@
 * [https://open.kattis.com/problems/longincsubseq Kattis longincsubseq] ([https://github.com/vfolunin/archives-solutions/blob/master/Kattis/longincsubseq.cpp решение: лексикографически минимальная LIS с сертификатом, O(NlogN)])
 * [https://open.kattis.com/problems/increasingsubsequence Kattis increasingsubsequence]
 === Наибольшая последовательность вкладываемых параллелепипедов ===

Ctrlalt: /* Наибольшая возрастающая подпоследовательность (LIS) */

2022-04-07T02:08:57Z

Наибольшая возрастающая подпоследовательность (LIS)

← Предыдущая версия		Версия от 02:08, 7 апреля 2022
Строка 110:		Строка 110:
	База рекурсии: d[0] = 1.		База рекурсии: d[0] = 1.

	Вид ответа: max(d[i]), где i ∈ 0..(n - 1). Сложность O(N<sup>2</sup>). ~~(*Данная задача может быть решена за O(NlogN), см. [[ACMP 1464]], [https://cses.fi/problemset/task/1145 CSES 1145].)~~		Вид ответа: max(d[i]), где i ∈ 0..(n - 1). Сложность O(N<sup>2</sup>).

	* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_3.swf Dean B. — Longest Increasing Subsequence]		* [http://people.cs.clemson.edu/~bcdean/dp_practice/dp_3.swf Dean B. — Longest Increasing Subsequence]
Строка 116:		Строка 116:
	* [[ACMP 122]]		* [[ACMP 122]]
	* [http://codeforces.ru/gym/100082/problem/A Codeforces #100082.A — Наибольшая возрастающая подпоследовательность]		* [http://codeforces.ru/gym/100082/problem/A Codeforces #100082.A — Наибольшая возрастающая подпоследовательность]

			(*Данная задача может быть решена за O(NlogN))
			* [[ACMP 1464]]
			* [https://cses.fi/problemset/task/1145 CSES 1145]
			* [https://open.kattis.com/problems/longincsubseq Kattis longincsubseq] ([https://github.com/vfolunin/archives-solutions/blob/master/Kattis/longincsubseq.cpp решение: лексикографически минимальная LIS с сертификатом, O(NlogN)])
			* [https://open.kattis.com/problems/increasingsubsequence Kattis increasingsubsequence]

	=== Наибольшая последовательность вкладываемых параллелепипедов ===		=== Наибольшая последовательность вкладываемых параллелепипедов ===

Ctrlalt: /* Ссылки */

2021-09-03T02:59:13Z

Ссылки

← Предыдущая версия		Версия от 02:59, 3 сентября 2021
Строка 407:		Строка 407:
	* [http://algorithmica.org/tg/dp-basics algorithmica.org — Введение в динамическое программирование]		* [http://algorithmica.org/tg/dp-basics algorithmica.org — Введение в динамическое программирование]
	* [http://algorithmica.org/tg/knapsack-gis-gcs algorithmica.org — Задача о рюкзаке, НВП и НОП]		* [http://algorithmica.org/tg/knapsack-gis-gcs algorithmica.org — Задача о рюкзаке, НВП и НОП]
	* [~~http~~://ejudge.~~btty~~.su/~~bmstu~~/~~addon~~/~~docs~~/~~articles~~/~~sbory2006~~-~~dp2~~.pdf Василевский Б. ~~—~~ Динамическое программирование по профилю]		* [https://ejudge.lksh.ru/archive/2011/07/B/files/dp-profile.pdf Василевский Б. — Динамическое программирование по профилю]
	* [~~http~~://~~github~~.~~com/petr-kalinin/progtexts/releases/download~~/~~v2014.11.01~~/~~05_dynprog~~.~~pdf~~ Калинин П. ~~—~~ Динамическое программирование]		* [https://notes.algoprog.ru/dynprog/index.html Калинин П. — Динамическое программирование]
	* [~~http~~://ejudge.~~btty~~.su/~~bmstu~~/~~addon~~/~~docs~~/~~articles~~/~~sbory2006-dp1~~.pdf Кириенко Д. ~~—~~ Динамическое программирование]		* [https://ejudge.lksh.ru/archive/2014/07/Cprime/stuff/Dynamic_programming.pdf Кириенко Д. — Динамическое программирование]
	* [http://www.youtube.com/watch?v=q_n2vzVNXE4&list=PLrS21S1jm43geDXVdeQy96P-f59pXeyPC&index=9 Маврин П. — Динамическое программирование]		* [http://www.youtube.com/watch?v=q_n2vzVNXE4&list=PLrS21S1jm43geDXVdeQy96P-f59pXeyPC&index=9 Маврин П. — Динамическое программирование]
	* [http://codeforces.com/blog/entry/6221 Codeforces — ДП учимся видеть состояния, придумывать переход]		* [http://codeforces.com/blog/entry/6221 Codeforces — ДП учимся видеть состояния, придумывать переход]

Ctrlalt в 19:11, 27 декабря 2020

2020-12-27T19:11:28Z

← Предыдущая версия		Версия от 19:11, 27 декабря 2020
Строка 415:		Строка 415:
	* [http://people.cs.clemson.edu/~bcdean/dp_practice people.cs.clemson.edu — Dynamic Programming Practice Problems]		* [http://people.cs.clemson.edu/~bcdean/dp_practice people.cs.clemson.edu — Dynamic Programming Practice Problems]

	[[Категория:~~Полный перебор и методы его оптимизации~~]]		[[Категория:Динамическое программирование]]

Ctrlalt в 12:46, 3 декабря 2020

2020-12-03T12:46:21Z

Внесённые изменения

Ctrlalt: /* Ссылки */

2020-02-15T17:21:29Z

Ссылки

← Предыдущая версия		Версия от 17:21, 15 февраля 2020
Строка 377:		Строка 377:

	== Ссылки ==		== Ссылки ==
	* [http://brestprog.~~neocities.org~~/~~lections~~/dp~~.html~~ brestprog~~.neocities.org —~~ Динамическое программирование на примерах]		* [http://brestprog.by/topics/dp/ brestprog — Динамическое программирование на примерах]
	* [http://brestprog.~~neocities.org~~/~~lections~~/bitmasks~~.html~~ brestprog~~.neocities.org —~~ Битовые маски. Динамическое программирование по маскам]		* [http://brestprog.by/topics/bitmasks/ brestprog — Битовые маски. Динамическое программирование по маскам]
	* [http://algorithmica.org/tg/dp-basics algorithmica.org — Введение в динамическое программирование]		* [http://algorithmica.org/tg/dp-basics algorithmica.org — Введение в динамическое программирование]
	* [http://algorithmica.org/tg/knapsack-gis-gcs algorithmica.org — Задача о рюкзаке, НВП и НОП]		* [http://algorithmica.org/tg/knapsack-gis-gcs algorithmica.org — Задача о рюкзаке, НВП и НОП]