c++ - How do I add this condition in this and make it optimal? -
the question link is: http://codeforces.com/problemset/problem/431/c
quite creative student lesha had lecture on trees. after lecture lesha inspired , came tree of own called k-tree.
a k-tree infinite rooted tree where:
- each vertex has k children;
- each edge has weight;
- if @ edges goes vertex children (exactly k edges), weights equal 1, 2, 3, ..., k.
the picture below shows part of 3-tree.
as dima, friend of lesha, found out tree, wondered: "how many paths of total weight n (the sum of weights of edges in path) there, starting root of k-tree , containing @ least 1 edge of weight @ least d?". dima find answer question. number of ways can rather large, print modulo 1000000007 (10^9 + 7). (open question link above picture of mentioned tree)
input
single line contains 3 space-separated integers: n, k , d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).output
print single integer — answer problem modulo 1000000007 (10^9 + 7).
so, tried develop recursive solution same. however, not able add constraint make sure edge of weight atleast d
should present. how can that? here recursive function:
void calc(int present, int total,int k) // here, present initialised 0. // total equal n reqd. // k value in question { if (total == present) { ans++; ans = ans%val; return; } else { ( int = 1; <= k; i++ ) { if (present+i <= total) return calc(present+i,total,k); } } }
just add following arguments function - d , whether have achieved constraint 1 of these edges @ least d
.
void calc(int present, int total,int k, int d, bool atleastd) {
change constraint increment if atleastd
.
if (total == present && atleastd) { ans++; ans = ans%val; return; } else { ( int = 1; <= k; i++ ) { if (present+i <= total)
when recursively call function, pass whether atleastd
has been achieved before, or if have satisfied constraint (i >= d
).
calc(present+i,total,k,d,atleastd || >= d);
in addition, removed return
in previous line. otherwise, code test 1 possible path - path weights == 1.
} } }
i assume ans
, val
globals, ans
answer problem, initialized 0, , val
modulo = 1000000007.
finally, while solution might solve small test cases, n <= 15
, slow n = 100.
to solve n = 100, suggest learn memoization , dynamic programming. leave exercise you.
Comments
Post a Comment