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

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

Восстановить пароль Регистрация
 
roanna
 Аватар для roanna
16 / 16 / 2
Регистрация: 11.11.2010
Сообщений: 88
06.06.2013, 23:27     Динамическое программирование. Разбиение абзаца на строки #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++ Динамическое программирование.Удаление строки
C++ динамическое программирование
Динамическое программирование. C++
Динамическое программирование C++
C++ Динамическое программирование
C++ Продолжение строки с нового абзаца в коде
C++ Динамическое программирование!

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
roanna
 Аватар для 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
Yandex
Объявления
09.06.2013, 15:29     Динамическое программирование. Разбиение абзаца на строки
Ответ Создать тему
Опции темы

Текущее время: 22:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru