@Handakai

Как решить эту комбинаторную задачу?

hgw7dQe.png
Я уже два часа бьюсь головой об стол, как же это решить? Дак еще нужно и написать универсальный алгоритм. Прошу помощи!!!
  • Вопрос задан
  • 35 просмотров
Пригласить эксперта
Ответы на вопрос 2
Adamos
@Adamos
Лучше побиться ручкой о бумажку. Написать образец и подумать, как бы решал это вручную.
В строке вас интересуют только единицы и ДЛИНА строки нулей МЕЖДУ ними.
Если единицы стоят подряд - есть один вариант разделить их.
Если между ними один ноль - есть два варианта.
Если два нуля - три варианта.
Если между первой и второй единицами один ноль, между второй и третьей - два, сколько всего вариантов?
Дальше сам.
Ответ написан
wataru
@wataru
Разработчик на С++, гуглер, экс-олимпиадник.
Представьте вашу строку, и нарисуйте палочки между двумя соседними битами там, где проходит граница блоков. Вопрос в задаче подсчитать количество способов расставить эти палочки правильно (стоит обязательно палочка в самом начале и самом конце, между любыми соседними палочками - ровно одна единица).

Из условия получается, что между двумя единицами, разделенными некоторым (может и пустым) количеством нулей, обязательно должна стоять ровно одна палка. Т.е. границы расстановки разных палок не пересекаются. есть одна между первой и второй единицей. одна между второй и третьей и т.д.

Вот и считайте, сколько вариантов поставить палку перед каждой единицей. Надо подсчитать расстояния между каждой парой единиц и перемножить. Если единиц вообще нет - ответ 0, если одна - то 1.

Можно сделать за один проход, если запоминать, где стояла предыдущая единица.

int64_t CountWaysToSplit(std::string s) {
  int last_one = -1;
  int64_t res = 1;
  for (int i = 0; i < s.length(); ++i) {
    if (s[i] == '1') {
      if (last_one >= 0) res *= i - last_one;
      last_one = i;
    }
  }
  return last_one >= 0 ? res : 0;
}
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы