Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

codeforces2k19's blog

By codeforces2k19, history, 9 months ago, In English,

I came across the solution to the problem:

http://codeforces.com/problemset/problem/189/A

can anyone explain me what is the approach to get this recursive relation(I am a beginner):

ll fun(ll n)

{

if(n<0)


    return INT_MIN;


if(n==0)


    return 0;


if(dp[n]!=-1)


    return dp[n];


dp[n]=max(fun(n-a)+1,max(fun(n-b)+1,fun(n-c)+1));


return dp[n];

}

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Let $$$f(n)$$$ be the maximal number of ribbon pieces of length $$$a$$$, $$$b$$$, and $$$c$$$, so that their sum is $$$n$$$.

Let's assume that you know the solution. For instance the optimal way to cut a ribbon of length $$$n$$$ is

$$$abaacb$$$

. If you remove the last piece $$$b$$$, you end up with

$$$abaac$$$

. Since

$$$abaacb$$$

was the optimal solution for $$$n$$$,

$$$abaac$$$

must be the optimal solution for

$$$n-b$$$

(if there would be a better solution for

$$$n-b$$$

, you can also improve the solution for $$$n$$$). This means that

$$$f(n) = 1 + f(n-b)$$$

.

Now back to the problem. Of course at the beginning you don't know the optimal solution. But you know that the last piece of the optima solution is $$$a$$$, $$$b$$$ or $$$c$$$. Therefore you can write

$$$f(n) = \max(1 + f(n-a), 1 + f(n-b), 1 + f(n-c))$$$

. If the optimal solution has a $$$b$$$ piece at the end,

$$$1 + f(b)$$$

will be the biggest one.

Now, to make a recursion stop, you need to define stop condition. Clearly

$$$f(0) = 0$$$

.

And we want that

$$$f(n) = -\infty$$$

if you cannot cut the ribbon in such a way. E.g. if $$$n = 7$$$ and

$$$a = 5, b = 6, c = 8$$$

, then you want that

$$$f(n = 7) = -\infty$$$

. To accomplish this, you can just define

$$$f(n) = -\infty$$$

if

$$$n < 0$$$

. If it is not possible to cut the ribbon correctly, then you remove elements from the back and reach a negative number (doesn't matter how you remove them).

To make this solution efficient, apply dynamic programming to it. In this code example they used Top-Down-DP.