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

Question

[Handakai]

Я уже два часа бьюсь головой об стол, как же это решить? Дак еще нужно и написать универсальный алгоритм. Прошу помощи!!!

Answer 1

[Adamos]

Лучше побиться ручкой о бумажку. Написать образец и подумать, как бы решал это вручную.
В строке вас интересуют только единицы и ДЛИНА строки нулей МЕЖДУ ними.
Если единицы стоят подряд - есть один вариант разделить их.
Если между ними один ноль - есть два варианта.
Если два нуля - три варианта.
Если между первой и второй единицами один ноль, между второй и третьей - два, сколько всего вариантов?
Дальше сам.

Comments

[Handakai]

А если строка начинается с нуля?
может же быть 01 и 010 и 0100
и тд

[Adamos]

Handakai, перечитайте условия. Сколько вариантов разбиения у приведенных вами строк?

Answer 2

[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;
}