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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Написание ровнялки текста. http://www.cyberforum.ru/cpp-beginners/thread81526.html
День добрый. Не могли бы вы помочь мне в решение одной проблемки. (новую тему заводить не стал, эта подходит) Проблемка состоит в написании ровнялки текста из файла (допустим c:\\1.txt) по ширине консоли (либо по введенной длинне строки. Т.е. если 20 то текст будет вводится в столбик, но это уже не обязательно). Тут уже есть несколько вариантов ровнялок, из них я от части понимаю варинт от...
C++ Работа с файлом!!! Помогите пожалуйста написать программу на языке си: Задан текстовый файл С, состоящий из произвольной последовательности буквенных символов. Упорядочить символы в алфавитном порядке, при этом все повторяющиеся символы должны быть удалены и переписать новый текст в файл D. http://www.cyberforum.ru/cpp-beginners/thread81485.html
C++ Структура с полями
Помогите пожалуйста, никак не могу реализовать эту программу((( Запись о товаре на складе представляет собой структуру с полями: номер склада, код товара, наименование товара, дата поступления на склад, срок хранения в днях, количество единиц товара, цена за единицу товара. Записи о товарах хранятся в файле. Реализовать функции: 1.1. Поиск по номеру склада 1.2. Поиск по коду товара 1.3....
C++ статический массив ----> динамический массив
Есть программа, нужно статический массив заменить на динамический. Как будет выглядеть? #include <iostream> #include <windows.h> #include <fstream> #include <cstdlib> #include <cstring> using namespace std; // Определение структуры struct sotrudnik
C++ скомпилировать структуру http://www.cyberforum.ru/cpp-beginners/thread81460.html
у меня проблемы с Visual Studio!!!!плз ктонить скомпилируйте это и скажите работает ли...пробовал на онлайн компиляторах - вроде ошибок нет,но знаю как работает!!плз можете проверить!ну очень срочно надо.. #include "stdafx.h" #include <fstream> #include <iostream> #include <string> #include <stdlib.h> #include <windows.h>
C++ Строки В заданном тексте везде заменить слово 1 на слово 2 (длины слов в общем случае не совпадают). Помогите, даже не знаю с чего начать. Хотя бы наводку дайте, как это сделать Добавлено через 41 минуту как реализовать саму замену одного слова на другое? подробнее

Показать сообщение отдельно
LeBron23
10 / 10 / 1
Регистрация: 18.11.2009
Сообщений: 47
29.12.2009, 23:42     Динамическое программирование
Есть минимум 3 способа решать это динамикой. Выложу самый медленный, но самый простой для понимания (n^4, N*M*N*M в нашем случае, для матрицы 100*100 в секунду укладывается).
Для начала находим сумму всех елементов во всех подмасивах с левым верхним углом в (1;1). Это делается примерно так:
C++
1
2
3
4
5
6
for (i=1;i<=N;i++)
{for (j=1;j<=M;j++){
cin>>t;
ar[i][j]=ar[i-1][j-1]+v[i]+g[j]+t;
v[i]+=t;g[j]+=t;
;};}
Считываем массив и на ходу заполняем таблицу динамики. в ar[i][j] у нас будет сумма элементов в прямоугольнике с углами в начале и этой клетке. в v и g - дополнительная информация, сумма по столбцам и строкам. Если массив уже дан (как в Вашем условии) - все то же самое, ну только не считываем, а работаем с готовым массивом (будет обращение к A[i][j]).
После этого можем приступать к самому перебору. Будем перебирать по 2 противоположным углам:
C++
1
2
3
4
5
6
7
for (i=1;i<=N;i++)
{for (j=1;j<=M;j++){
for(q=1;q<=i;q++){
for (t=1;t<=j;t++){
if (ar[i][j]-ar[i][t-1]-ar[q-1][j]+ar[t-1][q-1]>ans)
{ans=ar[i][j]-ar[i][t-1]-ar[q-1][j]+ar[t-1][q-1];}
;};};};}
В результате в ans будет ответ на задачу.
Чтоб понять, откуда "формула"
C++
1
if (ar[i][j]-ar[i][t-1]-ar[q-1][j]+ar[t-1][q-1]>ans)
- нарисуйте прямоугольники на бумажке, словамидолго расписывать.
 
Текущее время: 00:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru