спой дп лсорт подход
http://www.spoj.com/problems/LSORT/ Это проблема по спой
Это заявляет, что
Вам дана перестановка из n чисел от 1 до n без дубликатов.
Задача состоит в том, чтобы отсортировать эту перестановку в порядке возрастания. Есть еще один массив Q, в который мы вставляем элементы из данной перестановки P.
Вы должны реализовать N шагов для сортировки P. На i-м шаге P имеет N-i + 1 оставшихся элементов, Q имеет i-1 элементов, и вам нужно выбрать некоторый x-й элемент (из N-i + 1 доступных элементов) из P и поместите его слева или справа от Q. Стоимость этого шага равна x * i. Общая стоимость — это сумма затрат на отдельные этапы. После N шагов Q должен быть восходящей последовательностью. Ваша задача — минимизировать общую стоимость.
вход
Первая строка входного файла — T (T ≤ 10), количество тестовых случаев. Затем следуют описания T-тестов. Описание каждого теста состоит из двух строк. Первая строка содержит одно целое число N (1 ≤ N ≤ 1000). Вторая строка содержит N различных целых чисел из множества {1, 2, .., N}, N-элемент перестановки P.
Выход
Для каждого теста ваша программа должна написать одну строку, содержащую одно целое число — минимальную общую стоимость сортировки.
Теперь я понял, дп
Мое рекуррентное соотношение гласит, что для получения наиболее оптимальных значений от элементов, имеющих значения от i до j, мне нужно будет вставить либо $ i $ спереди, либо $ j $ сзади.
Стоимость вставки я спереди = дп [+ 1] [J]+стоимость добавления элемента я впереди
Стоимость вставки J сзади = дп [I] [J-1] +стоимость добавления элемента j на спине
и я должен взять минимум из них. Ответ будет dp [1] [n]
for(l=1;l<=n;l++) //length of current permutation Q
{
for(i=1;i<=n-l+1;i++) //starting value of permutation Q
{
j=i+l-1; //ending value of permutation Q
dp[i][j]=min(dp[i+1][j]+l*xi,dp[i][j-1]+l*xj);//chosing wether to insert i at start or j at end
}
}
здесь xi = индекс элемента я с начала перестановки П.
и yi = индекс элемента J с начала перестановки П.
ans будет dp [1] [n]
Но я не могу понять XI и XJ
Пожалуйста помоги
Решение
Вы можете попробовать переосмыслить свое состояние DP.
Для меня я бы использовал dp [startQ] [endQ], где dp [startQ] [endQ] означает стоимость, которую я понес за это время, чтобы «отсортировать» значения startQ to endQ в массиве Q.
Если вы знаете, что находится в массиве Q (включая целые числа от startQ до endQ), можно легко перестроить массив P, просто удалив / проигнорировав все целые числа в startQ и endQ.
Для каждого состояния dp [startQ] [endQ], так как можно добавить только переднюю или заднюю часть Q,
dp [startQ] [endQ] может быть только:
dp [startQ] [endQ-1] + стоимость добавления endQ
dp [startQ-1] [endQ] + стоимость добавления startQ
с базовыми случаями, являющимися
dp [i] [i] = 0;
Эти состояния могут быть вычислены, и ответ может быть найден в dp [1]] [n]; (при условии, что это один индексированный).
Однако я не думал об эффективном способе вычисления x если бы он был закодирован сверху вниз, где все вычисления могут быть выполнены в O (N ^ 2 log N) с использованием восходящего DP со структурой данных для вычисления x в каждом штате.
Я оставлю последние детали для вас, чтобы закодировать :), но я могу помочь больше, если потребуется.
Другие решения