codeforces2k19's blog

By codeforces2k19, history, 5 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

»
5 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.