Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
mybook11.05.12.doc
Скачиваний:
15
Добавлен:
01.07.2025
Размер:
6 Мб
Скачать
☆

Решение

Для начала заметим, что длины удочек никак на ответ не влияют. Наша задача, фактически, состоит в следующем: требуется найти количество разложений K в сумму N различных натуральных чисел. Вычтем из наименьшего числа в разложении 1, у второго по величине - 2, и т.д., из N-ого - N. Заметим, что таким образом мы споставляем каждому разложению K на N неравных натуральных множителей разложение числа L = K-N(N+1)/2 в сумму N целых неотрицательных, не обязательно неравных, чисел. Если у нас получилось L<0, то количество вариантов равно нулю.

Обозначим это количество через aL,N. Выведем рекуррентное соотношение на aL,N. Заметим, что все разложения разбиваются на две группы:

  • разложения, в которых хотя бы одно из чисел равно 0;

  • разложения, в которых все числа больше нуля.

Если мы из разложения первого типа выкинем член, равный нулю, то мы получим уже разложение числа L (сумма ен менялась) на N-1 слагаемое. Следовательно, количество разложений первого типа равно aL,N-1. С разложениями второго типа поступим иначе: вычтем из каждого слагаемого в разложении по 1. В результате, мы получим разложение числа L-N на N слагаемых. Значит, разложений второго типа ровно aL-N,N. Итак, мы получили рекуррентное соотношение:

aL,N=aL,N-1 + aL-N,N

Остается добавить, что a0,N = 1 для любого N и aL,1=1 для любого L. С помощью этих соотношений легко написать программу, которая будет решать данную задачу. Вычисляем элементы этого массива последовательно.

динампрогрзадачи

Задача 31 Палиндромы

Непустая строка называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Пусть задана строка S, состоящая из N прописных букв латинского алфавита. Вычеркиванием из нее некоторых букв нужно получить палиндром.

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

Входные данные:

В единственной строке входного файла INPUT.TXT записано N букв слова S (1 <= N <=60).

Выходные данные:

В единственной строке выходного файла OUTPUT.TXT должно содержаться найденное число способов.

Пример входного и выходного файла

INPUT.TXT

OUTPUT.TXT

BAOBAB

22

program palindrom;

var i, j, k, l, n, p, sum : integer;

a : array[1..60,1..60l] of byte; a[i,j] – количество способов вычеркивания с i по j

s : string; позиции

begin

assign(input,'input.txt’);reset(input);

assign(output,'output.txt'); rewrite(output);

readLn(s);

n := length(s);

fillchar(a,sizeof(a),0);

for i:=1 to n do a[i,i]:=1;

for k:=1 to n do заполняем массив

for i:=1 to n-k do перебираем позиции

begin

j:=i+k;

if s[i] = s[j] если символы совпадают

then sum := a[i+1,j] + a[i,j-1] + 1

else sum := a[i+1,j] + a[i,j-1] - a[i+1,j-1] ;

end;

write(a[1,n]);

close(input); close(output);

end.

динампрогрзадачи

Задача 32  График работы

Нанимая на работу нового охранника, директор фирмы вручил ему список из N–1 интервала времени [t1; t2], [t2; t3], ... , [tN – 1; tN] и предложил самому составить график его дежурств. Охраннику разрешается выбрать в качестве рабочих смен любые промежутки времени [tk ; tm] (k  m), удовлетворяющие следующим требованиям:

1) первый и последний интервалы [t1; t2] и [tN – 1; tN] он должен отработать обязательно;

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

Требуется разработать программу для составления графика, при котором суммарное время работы охранника было бы минимальным.

Формат входных данных:

Первая строка входного файла содержит одно целое N — общее количество моментов времени в списке (2  N  5000). Каждая i-ая из последующих N строк содержит по одному целому числу ti (0  ti  60 000).

Формат выходных данных:

Первая строка выходного файла должна содержать одно число — суммарное время работы охранника. Следующие строки содержат по два разделенных пробелом числа, определяющих моменты начала и конца каждой смены.

Пример:

Input.txt

Output.txt

5

2

5

12

14

20

11

2 5

12 20

Идея решения. Использование схемы динамического программирования.

program gvozdiki;

const nmax=5000;

var d,k,n,i,j:integer;

a:array[1..nmax] of longint;

b:array[0..nmax] of longint;

procedure init;

var p:integer;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

read(n); считываем количество моментов времени

for i:=1 to n do read(a[i]); считываем времена

for i:=1 to n-1 do сортируем времена по возрастанию

for j:=i+1 to n do

begin

if a[i]>a[j] then

begin

p:=a[i];

a[i]:=a[j];

a[j]:=p;

end;

end;

close(input);

end;

function min(x,y:integer):integer; находит минимальное из двух чисел

begin

if x<y then min:=x

else min:=y;

end;

procedure solve; решение

begin

b[0]:=0; фиктивный самый меньший момент времени

b[1]:=60000; расстояние от фиктивного до первого =

бесконечности

for i:=2 to n do перебираем моменты времен

begin

b[i]:=min(b[i-1],b[i-2])+a[i]-a[i-1]; выбираем минимальный из двух возможных

end; промежутков

end;

procedure out;

begin

write(b[n]); close(output);

end;

begin init; solve; out;end.

динампрогрзадачи

Задача 34 О распиле палки решения нет

Дан отрезок (палка) [0,N], который нужно распилить в помеченых местах L1 , L2, ... , Lk. Числа N, Li — натуральные, 1 <= N <= 1000000, 1 <= k <= 200, 0 < Li < N. Числа Li разные. За один раз мы можем распилить один отрезок на два и заплатить за это цену, равную его длине. Сделайте распилы в помеченых местах, заплатив за это минимальную цену.

Эта задача решается методом динамического программирования. Идея динамического программирования заключается в двух моментах

  • параметризация задачи, то есть введение множества задач, запараметризованного одним или несколькими целочисленными параметрами, так что при максимальном значении параметров мы получаем ту задачу, которую нам нужно решить, а при маленьких значениях параметров получаем простые задачи, для которых мы можем сразу дать ответ

  • хранение в памяти вычисленных ответов для множества задач, и использование их при поиске ответов на задачи с большими значениями параметров

В нашем случае мы вводим такое параметрическое множество:

  • задача A[i][j] есть "найти минимальную цену распила палки [Li,Lj] во всех её внутренних метках

Таких задач ( k * (k-1) ) /2. Обозначим a[i][j] ответ на задачу A[i][j], а именно

  • a[i][j] есть минимальная цена распила палки [Li,Lj]

Нас интересует только элементы матрицы a[i][j] (массива) с j > i.

Понятно, что на диагонали и на второй диагонали матрицы стоят нули. Заполним остальные ячейки массива a "плюс бесконечностью" (в программе это будет просто очень большое число, например N*k + 1).

После этого диагональ за диагональю будем вычислять элементы массива a.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]