Примеры

Вывод

Ввод

Пример

Вывод

Ввод

Пример

2 5 3 4 6 1

2 3 4 6

Будем проходить последовательность от конца к началу и заполнять два массива C и D. В первом массиве для каждого элемента найдем длину наибольшей возрастающей подпоследовательности от этого элемента до конца. Первоначально массив можно инициализировать единицами, считая, что каждый элемент образует возрастающую подпоследовательность, состоящую только из него самого.

Во втором массиве для каждого элемента будем сохранять индекс следующего элемента в максимальной подпоследовательности, начинающейся от этого элемента.

Пусть I – номер текущего элемента, и оба массива заполнены для индексов с I+ 1 по N. В цикле по J будем перебирать все элементы от I+ 1-го до последнего. Если окажется, что X_I £ X_J, то элемент X_I может дополнить подпоследовательность, начинающуюся с элемента X_J. Найдем номер J, для которого длина C_J такой подпоследовательности максимальна. Положим C_I = C_J + 1 и D_I = J. Сохраним номер, начиная с которого максимальная возрастающая подпоследовательность оказалась самой длинной.

На втором проходе уже в прямом направлении по массиву D, начиная с найденного номера, восстановим искомую подпоследовательность.

Рассмотрим, например, при N=6 последовательность 6, 3, 9, 4, 7, 5. Для нее

1) C₆ = 1, D₆ = 0 – признак отсутствия больших элементов;

2) C₅ = 1, D₅ = 0;

3) C₄ = Max(C₅, C₆) + 1 =2, D₄ = 5 (подходит и D₄ = 6);

4) C₃ = 1, D₃ = 0;

5) C₂ = Max(C₂, C₃, C₄, C₅, C₆) + 1 =3, D₂ = 4;

6) C₁ = Max(C₃, C₅) =2, D₁ = 3.

Максимальное значение C_I достигнуто при I = 2. Одна из максимальных возрастающих подпоследовательностей 3, 4, 7 находится с помощью сохраненных в массиве D индексов 4 и 5.

Ниже приводится текст программы.

Program Posledov;

Const

R=5000; {максимальный размер последовательности}

Var

N: integer; {заданный размер последовательности}

X: array[1..R] of word;

C: array[1..R] of integer;

{C[i] - длина наибольшей возрастающей последовательности,

начинающейся с X[i]. Если подпосл. только из X[i], то 1}

D: array[1..R] of integer;

{D[i] - номер j - следующего числа X[j] в наибольшей

возрастающей подпоследовательности, начинающейся с X[i].

Если подпоследовательность только из X[i], то 0}

i,j,k,Max,IndMax: integer;

Fin,Fout: text;

Begin

Assign(Fin,'input.txt');

Reset(Fin);

ReadLn(Fin,N);

For i:=1 to N do Read(Fin,X[i]);

Close(Fin);

C[N]:=1; {длина подпосл., начинающейся с последнего элемента}

Max:=1; {наибольшая длина среди всех подпоследовательностей}

IndMax:=1; {начальный индекс наибольшей подпослед.}

For i:=N-1 downto 1 do

begin

C[i]:=1; D[i]:=0;

{если от X[i] подпоследовательность не найдется}

For j:=i+1 to N do

if (X[i]<X[j]) and (C[j]>=C[i]) then

{ C[j]>=C[i] с учетом добавления X[i] }

begin

C[i]:=C[j]+1; {к подпосл. добавляется X[i]}

D[i]:=j;

if C[i]>Max then

begin

Max:=C[i];

IndMax:=i;

end

end

end;

Assign(Fout,'output.txt');

Rewrite(Fout);

k:=IndMax;

WriteLn(Fout,C[k]);

Repeat

Write(Fout,X[k],' ');

k:=D[k];

Until k=0;

Close(Fout)

End.

Следующая задача динамического программирования является вариацией классической задачи о рюкзаке.

Свинья-копилка. Для того чтобы начать свой бизнес, юный коммерсант решил накопить немного денег. С этой целью он отыскал свинью-копилку и начал собирать деньги. Требуется написать программу, которая определяла бы минимальную сумму денег, которая может находиться в копилке, зная её вес без монет, вес с монетами и вес монет каждого типа.

Ввод из файла INPUT.TXT. В первой строке содержатся два целых числа: E – вес пустой копилки (1 ≤ E ≤10000); F – вес копилки, заполненной монетами (1 ≤ E ≤ F ≤ 10000). Вторая строка содержит целое число N (1≤ N ≤500) — количество типов монет. Каждая из последующих N строк служит для описания монет заданных типов и содержит по два целых числа — P_i и W_i (1 ≤ P_i ≤ 30000, 1 ≤ W_i ≤ 10000, 1 ≤ i ≤ N), где P_i — достоинство монеты i -го типа, а W_i — ее вес.

Вывод в файл OUTPUT.TXT. В единственной строке выводится значение минимальной суммы денег, которая может находиться в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то выходной файл должен содержать No.

10 110

1 1

30 50

Организуем цикл по увеличению M - чистого веса копилки. Если некоторый вес достижим, и в копилке есть монета определенного вида i, то вес M-Wi тоже достижим, а для него уже рассчитана минимальная стоимость монет. Иными словами, нужно найти MIN [(M-Wi)+Pi], учитывая i -ю монету, по всем видам монет, для которых вес M-Wi достижим. Расчет ведется до значения M, равного найденному по исходным данным значению чистого веса.

Program Kopilka;

Var

N,E,F,L: integer;

{число видов, вес пустой копилки, вес копилки с монетами, вес нетто}

Nmax: integer;

P: array [1..500] of integer; {ценность монет}

W: array [1..500] of integer; {вес монет}

Fin,Fout: text;

i,M: integer;

Cmin: array [0..10000] of longint;

{минимальные суммы в зависимости от веса}

S: longint;

Begin

Assign(Fin,'input.txt');

Reset(Fin);

ReadLn(Fin,E,F);

ReadLn(Fin,N);

For i:=1 to N do ReadLn(Fin,P[i],W[i]);

Close(Fin);

L:=F-E; {чистый вес монет}

Cmin[0]:=0; {сумма денег пустой шкатулки}

For i:=1 to L do Cmin[i]:=-1;

{инициализация: вес недостижим}

For M:=1 to L do {M - общий вес монет}

begin

S:=MaxLongInt; {для поиска MIN ценности монет}

For i:=1 to N do

if (M>=W[i]) and (Cmin[M-W[i]]<>-1) then

{i-я монета может быть последней в наборе}

if Cmin[M-W[i]]+P[i]<S then S:=Cmin[M-W[i]]+P[i];

{сумма минимальна с учетом последней монеты}

if S< MaxLongInt then Cmin[M]:=S;

end;

Assign(Fout,'output.txt');

Rewrite(Fout);

if Cmin[L]=-1 then WriteLn(Fout,'No')

else WriteLn(Fout,Cmin[L]);

Close(Fout)

End.

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

Следующая задача динамического программирования имеет прототипом известную задачу о камнях. Она во многом похожа на рассмотренную, но имеет свои особенности.

Суммы. Дано N целых чисел A ₁, A ₂,..., A_N. Требуется найти количество различных значений сумм вида k ₁ A ₁ + k ₂ A ₂ +... + k_NA_N.

Ввод из файла INPUT.TXT. В первой строке находится число N, во второй - A ₁, A ₂,..., A_N через пробел.

Вывод в файл OUTPUT.TXT. Вывести одно число - количество различных значений сумм.

Ограничения: 1 ≤ N ≤ 500, 0 ≤ A_i ≤ 100, 0 ≤ k_i ≤ 1, все числа целые, время 2 с.

Дата добавления: 2014-01-11