Как добавить это условие в это и сделать его оптимальным?

Question

Ссылку вопрос: http://codeforces.com/problemset/problem/431/C

Совсем недавно творческий студент Леша была лекция на деревьях. После лекция Леша была вдохновлена ​​и придумала дерево своего , которое он назвал k-деревом.

K-дерево представляет собой бесконечное корневое дерево, где:

• каждая вершина имеет ровно к детям;
• каждый край имеет некоторый вес;
• если мы посмотрим на края, которые идут от некоторой вершины к ее дочерним элементам (ровно k краев), то их веса будут равны 1, 2, 3, ..., k.

На рисунке ниже показана часть 3-х.

Как только Дима, хороший друг Леши, узнал о дереве, он сразу спрашивает: «Сколько пути общего вес п (сумма всех весов ребер в путь), начиная с корня из k-дерева и также содержащего, по меньшей мере, один край веса при наименее d? ". Помогите Диме найти ответ на его вопрос. Поскольку количество способов может быть довольно большим, напечатайте его по модулю 1000000007 (10^9 + 7). (Открыть ссылка вопрос выше для изображения упомянутого дерева)

ввода
Одна строка содержит пробел три целых числа: N, K и D (1 ≤ N, K ≤ 100; 1 ≤ d ≤ K).

Выход
печати одно целое число - ответ на задачу по модулю 1000000007 (10^9 + 7).

Итак, я попытался разработать рекурсивное решение для того же самого. Тем не менее, я не могу добавить ограничение, чтобы убедиться, что край веса atleast d должен присутствовать. Как я могу это сделать? Вот моя рекурсивная функция:

void calc(int present, int total,int k) // Here, present is initialised to 0. 
             // total is equal to n that is reqd. 
             // k is the value in the question 
{ 
    if (total == present) 
    { 
     ans++; 
     ans = ans%val; 
     return; 
    } 
    else 
    { 
     for (int i = 1; i <= k; i++) 
     { 
      if (present+i <= total) 
       return calc(present+i,total,k); 
     } 
    } 
} 

Answer 1

Просто добавьте следующие аргументы вашей функции - d и если вы достигли ограничения, что один из этих краев, по крайней мере d.

void calc(int present, int total,int k, int d, bool atleastd) 
{ 

Изменить ограничение для увеличения только если atleastd.

if (total == present && atleastd) 
    { 
     ans++; 
     ans = ans%val; 
     return; 
    } 
    else 
    { 
     for (int i = 1; i <= k; i++) 
     { 
      if (present+i <= total) 

Когда вы рекурсивный вызов вашей функции, передать ли atleastd уже достигнута ранее, или если вы только удовлетворенный это ограничение (i >= d).

   calc(present+i,total,k,d,atleastd || i >= d); 

Кроме того, я удалил return в предыдущей строке. В противном случае код будет только тест 1 возможный путь - путь, где все веса == 1.

 } 
    } 
} 

Я предполагаю, что ans и val являются Глобал, ans является ответ на проблему, инициализируется в 0, и val является по модулю = 1000000007.

---

Наконец, в то время как это решение может решить небольшие тестовые случаи, когда n <= 15, это будет слишком медленным для п = 100.

для решения при п = 100, I sugge st, чтобы узнать о memoization и dynamic programming. Я оставлю это как упражнение для вас.