hulk_baba's blog

Difficulty while constructing solution in DP
By hulk_baba, history, 7 years ago, In English

Please look at problem here. I figured out how to do it: 1. I will check among all possible quasibinary numbers which provides me least numbers of such numbers whose sum is equal to n(the given number) 2. I memoize the solution. Basic DP stuff. 3. In all my tests I got correct answer for number of numbers but I can't construct the solution i.e actual numbers which form the solution. Can you help me with this.

I have submitted my solution here

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Save curr in an array and then trace back the numbers that you chose. Something like

int cur = n;

while(cur){

ans.push_back(saved[cur]);

cur -= saved[cur];

}

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Do smth like that

int powten = 1;

for(int i=0;i<7;i++){

    int x = (n / powten) % 10;

    for(j=0;j<x;j++) ans[j] += powten;

    cnt = max(cnt,x);

    powten *= 10;

}

Then output cnt then newline and array ans

→ Reply