Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
h3mbr0
212 / 55 / 13
Регистрация: 12.03.2012
Сообщений: 281
#1

Задачка на динамическое программирование - C++

01.12.2013, 13:27. Просмотров 580. Ответов 0
Метки нет (Все метки)

Доброго времени суток!
Несколько часов не могу решить одну нетрудную задачку:
Задача «Роман в томах»
В романе известного писателя N глав. В i-той главе имеется ai страниц. Издатель хочет
издать этот роман в K томах так, чтобы объем самого «толстого» тома был минимален. В
каждом томе главы располагаются по порядку своих номеров.
Требуется написать программу, которая вычисляет количество страниц в самом
«толстом» томе.
Описание входных данных
Входной текстовый файл input.txt содержит в первой строке число N – количество
глав в романе (1 ≤ N ≤ 100). Во второй строке через пробел записаны N чисел – количество
страниц в каждой главе. Количество страниц в романе не превышает 32767. В третьей строке
записано число K – количество томов (1 ≤ K ≤ N).
Описание выходных данных
Выходной файл output.txt должен содержать количество страниц в самом
«толстом» томе.
Примеры входных и выходных данных
1)
input.txt
3
1 2 1
2
output.txt
3
2)
input.txt
4
1 2 1 1
3
output.txt
2

есть решение на паскале:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var
a, b, c : array [1..100] of integer;
n, k, i, j, s, min, l, t : integer;
function max(a,b:integer):integer;
begin
if a>b then max:=a else max:=b
end;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(n);
for i:=1 to n do read(a[i]);
read(k);
s:=a[1]; b[1]:=a[1];
for i:=2 to n do
begin s:=s+a[i]; b[i]:=s end;
for j:=2 to k do
begin
for i:=j to n do
begin
min:=maxint; s:=0;
for l:=1 to i-j+1 do
begin
s:=s+a[i-l+1];
t:=max(s,b[i-l]);
if t<min then min:=t
end;
c[i]:=min
end;
b:=c
end;
write(b[n])
end.
и теория:
http://plasmon.rghost.ru/50563372/image.png
Задача: написать на си или с++ (только вычислительную часть)
ну или объяснить по какому принципу происходит вычисление, только более доступным языком)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.12.2013, 13:27     Задачка на динамическое программирование
Посмотрите здесь:

Динамическое программирование - C++
Мячик прыгает по лестнице, состоящей из N ступенек, строго сверху вниз. За один прыжок он может отпрыгнуть на не более M ступенек....

динамическое программирование - C++
Народ помогите плиз найти алгоритм решения следующей задачи. На посвящение в студенты собрались все первокурсники. Некоторые из них знают...

Динамическое программирование - C++
народ помогите пожалуйста. есть задача Написать программу, позволяющую вычислить количество чисел, не содержащих нули, сумма цифр...

Динамическое программирование - C++
Усложнили задачу мне.... : Дан массив A. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным...

Динамическое программирование - C++
Помогите решить задачу! Я что-то особо не соображу... 1.Написать программу, реализующую действия: а. сформировать ленточную матрицу...

Динамическое программирование - C++
Не понимаю динамических структур, списков, работы с ними. Посоветуйте источник изучения. Что-то вроде того что написано здесь...

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

ДП Динамическое программирование - C++
ограничение времени на тест: 0.5 сек. ограничение памяти на тест: 65536 KB. Рассмотрим все строки длины N, состоящие только из букв...

Динамическое программирование - C++
Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт У Пети есть полоска бумаги, разделенная на N клеток. Он хочет...

Динамическое программирование - C++
Подскажите что не так в решении. #include &lt;iostream&gt; #include &lt;stdio.h&gt; using namespace std; const int N = 5001; int...

Динамическое программирование - C++
Есть такая задача: Дана схема стены, необходимо проверить можно ли построить данную стену заданным набором кирпичей. Кирпич высот 1, а...

Динамическое программирование - C++
Задача: Есть n работников и n работ. Необходимо найти максимальную суммарную производительность. Каждый работник может выполнять только...


Искать еще темы с ответами

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru