Динамическое программирование, задача про роботов

[Eida]

[динамическое программирование]

В Умном городе сортировкой стеклотары занимаются роботы. Их задача - разделить бутылки на темные и светлые.

Сортировка происходит так: n бутылок стоят на конвейере, два робота одновременно захватывают бутылки с начала конвейере и сбрасывают их в контейнеры; после этого лента конвейера движется, и роботам доступны следующие бутылки. Один робот работает с темными бутылками, а другой - со светлыми. Каждый робот может взять не более k бутылок. Поэтому, если на конвейере стоят подряд более чем k бутылок одного цвета, одному из роботов нечего взять с конвейера.

В Умном городе не любят, когда роботы простаивают, и самим роботам это тоже не нравится. Поэтому всех интересует вопрос: сколько существует вариантов расстановки n бутылок так, чтобы бутылок одного цвета, стоящих подряд, было не более чем k. Ответьте на этот вопрос.



Пример. n=4, k=2. Есть 10 вариантов:

TTCT TTCC TCTT TCTC TCCT CTTC

CTCT CTCC CCTT CCTC



Входные данные:

В единственной строке входных данных заданы два целых числа n, k (1 <= n, k <= 10^6) (1 <= nk <= 10^6)



Выходные данные:

Единственное целое число — ответ на задачу. Так как ответ может быть очень большим числом, выведите его по модулю 10^9 + 7

Sample Input:

4 2
Sample Output:

10


Напишите код, пожалуйста

[Пётр Седов]

Пока приходит на ум вот такой простой код:

#include <assert.h>
#include <iostream>
#include <vector>

using namespace std;

enum bottle_type_t {_bottle_type_light, _bottle_type_dark};

int _bottles_count; // n
int _max_mono_len; // k
vector<bottle_type_t> _bottles;
int _valid_cases_count = 0;

void place_light_bottles(int start_pos);
void place_dark_bottles(int start_pos);
void add_valid_case();

int main() {
  cin >> _bottles_count >> _max_mono_len;
  _bottles.resize(_bottles_count);
  place_light_bottles(0);
  _valid_cases_count *= 2; // вместо "place_dark_bottles(0)"
  cout << "valid cases count = " << _valid_cases_count << endl;
  return 0;
}

void place_light_bottles(int start_pos) {
  assert(start_pos < _bottles_count);
  for (int i = 0; i < _max_mono_len; i++) {
    _bottles[start_pos + i] = _bottle_type_light;
    if (start_pos + i + 1 == _bottles_count) { // если дошли до конца
      add_valid_case();
      break;
    }
    // за светлыми бутылками размещаем тёмные бутылки
    place_dark_bottles(start_pos + i + 1);
  }
}

void place_dark_bottles(int start_pos) {
  assert(start_pos < _bottles_count);
  for (int i = 0; i < _max_mono_len; i++) {
    _bottles[start_pos + i] = _bottle_type_dark;
    if (start_pos + i + 1 == _bottles_count) { // если дошли до конца
      add_valid_case();
      break;
    }
    // за тёмными бутылками размещаем светлые бутылки
    place_light_bottles(start_pos + i + 1);
  }
}

void add_valid_case() {
  // выводим на консоль подходящий вариант расстановки бутылок (для отладки)
  for (int i = 0; i < _bottles_count; i++) {
    switch (_bottles[i]) {
    case _bottle_type_light: {cout << 'l'; break;}
    case _bottle_type_dark: {cout << 'd'; break;}
    }
  }
  cout << endl;

  _valid_cases_count++;
}

Но это не динамическое программирование, будет медленно работать для больших n. Проверку на переполнение (overflow) не делал.