Блог пользователя deinier

Help in Abbyy Cup B problem.

Автор deinier, 11 лет назад, По-английски

Hello community:

I am trying to solve B task in Abbyy Cup and I would like to know how can I build all the possible sums in an array of integers.

I am making all the components in the graph using dfs and I am using the PosF() function to get the position of X in its component.

At the end, I have a vector with the size of each component but I need to get all possible sums. Maybe it would be solved either by dp or by two pointers but right now I do not know how solve it.

It is something like this: Array of Components (I do not add the component that include X) = {3 8 1} and X is in the first position in its component -> Possible positions in the queue: 1, 1 + 1, 3 + 1, 4 + 1, 8 + 1, 9 + 1, 11 + 1, 12 + 1.

Here is my solution.

Thanks in advance.

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
    sol[posx] = 1;
    ncomp = comp.size();
    for(i=0;i<ncomp;i++)
     {
		for(j=n;j>=0;--j)
			if(sol[j])
				sol[j+comp[i]] = 1;
     }
→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    Thank you very much, I was so close ... Thanks, Thanks, Thanks. Here my AC solution. I copied and pasted your code. Great!!!!! I understood the dp, it is awesome.

    → Ответить