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

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

Войти
Регистрация
Восстановить пароль
 
roanna
16 / 16 / 2
Регистрация: 11.11.2010
Сообщений: 88
#1

Динамическое программирование. Разбиение абзаца на строки - C++

06.06.2013, 23:27. Просмотров 879. Ответов 1
Метки нет (Все метки)

Условие:
В абзаце есть блоки разной высоты (напрмер, обычные слова и математические символы). Абзац длинный, поэтому его нужно разбить на строки. Высота строки определется по наивысшему из блоков в ней. Высота абзаца равна сумме высот всех строк. Длина каждой строки определяется как суммарная ширина блоков, включенных в эту строку (учитывать пробелы не нужно). Возможность разбиения блока для переноса со строки на строку не рассматривается. Изменять порядок следования блоков нельзя. Нужно найти такое разбиение абзаца на строки, чтобы высота абзаца была минимальной. Ширина и высота каждого блока (w(i), h(i)) и максимально допустимая длина строки TW задаются во входных данных.

Проблема:
С нахождением минимальной вісоті вопросов нет - динамика и все. Столбняк у меня уже неделю вызывает то, как можно высчитать количество строк и количество блоков в каждой строке соответственно.

У кого какие есть идеи?

Добавлено через 6 часов 1 минуту
Что, совсем никак???

Добавлено через 22 часа 37 минут
Ноль???
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.06.2013, 23:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Динамическое программирование. Разбиение абзаца на строки (C++):

Динамическое программирование.Удаление строки - C++
Дана строка S, состоящая из n маленьких латинских букв. За один ход Вам разрешается удалить один или несколько подряд идущих одинаковых...

Продолжение строки с нового абзаца в коде - C++
Собствено, как: printf("Hello World"); Без использования std::string! Именно константым литералом

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
roanna
16 / 16 / 2
Регистрация: 11.11.2010
Сообщений: 88
09.06.2013, 15:29  [ТС] #2
Вот нахождение минимальной высоты абзаца:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Ex_803::Paragraph()
{
   for(int i = 1; i <= N; i++)
   {
      int k = i - 1;
      int nMax_h = h[i];
      int nSumOfWeigth = w[i];
      int nMin = T[k] + h[i];
 
      while(k >= 0 && nSumOfWeigth <= TW)
      {
         if(h[k] > nMax_h)
            nMax_h = h[k];
         if((nMax_h + T[k]) < nMin)
            nMin = nMax_h + T[k];
         nSumOfWeigth += w[k--];
      } // while
      m_aOptimal[i] = k+1;
      T[i] = nMin;
   } // for
} // Paragraph
А вот лобовая реализация разбития строк:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   int aLine[5001]; // number of blocks for each i line
   int nLC; // number of lines
   
   nLC=1;
   for(int i = 1; i <= N; i++)
   {
      if(T[i] == h[i] && T[i] != T[i-1])
         aLine[nLC]++;
      else
      {
         if(T[i] == T[i-1])
            aLine[nLC] ++;
         else if(T[i] == h[i]+T[i-1])
            aLine[++nLC]++;
         else
         {
            nLC++;
            aLine[nLC] = i - m_aOptimal[i];
            aLine[nLC-1] = aLine[nLC-1] - aLine[nLC] +1;
         }
      }
   }
Следующие тесты программа проходит, но так как это задача олимпиадная, решение последующих (неизвестных мне вариантов) тестов неверное. E-olimp выдает ошибки связанные с тем, что моя программа выдает или слишком мало, или слишком много данных. Если ни у кого нет идей и желания помочь мне с алгоритмом, буду очень признательна, если вы поможете мне с тестированием.
HTML5
1
2
3
4
5
6
7
8
  INPUT     OUTPUT
  7 6         5
  3 1         3
  2 1         2
  3 3         3
  1 1         1
  3 3
  3 1
HTML5
1
2
3
4
5
  INPUT     OUTPUT
  2 3         7
  1 2         2
  1 4         1
  1 5         2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.06.2013, 15:29
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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