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

Форум программистов и сисадминов Киберфорум

Войти

Регистрация
Восстановить пароль

h3mbr0

298 / 107 / 31

Регистрация: 12.03.2012

Сообщений: 449

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

01.12.2013, 13:27. Показов 3074. Ответов 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

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
Задача: написать на си или с++ (только вычислительную часть)
ну или объяснить по какому принципу происходит вычисление, только более доступным языком)

cpp_developer

Эксперт

20123 / 5690 / 1417

Регистрация: 09.04.2010

Сообщений: 22,546

Блог

01.12.2013, 13:27

Ответы с готовыми решениями:

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

Динамическое программирование
Столкнулся с такой задачей. Есть 6 фигурок площадью 3. Нужно узнать, сколькими способами можно полностью замостить ими поле n на m,...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

raxper

Эксперт

30234 / 6612 / 1498

Регистрация: 28.12.2010

Сообщений: 21,154

Блог

01.12.2013, 13:27

Помогаю со студенческими работами здесь

Динамическое программирование!
#include <cstdio> #include <algorithm> using namespace std; int a, n, m; int main() { scanf(" %d %d", &n,...

Динамическое программирование
очень нужна реализация(завтра дедлайн) Будем называть натуральное число трипростым, если в нем любые подряд идущие 3 цифры образуют...

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

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

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

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

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

Наверх