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

Help in Abbyy Cup B problem.

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

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
  • Проголосовать: не нравится

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 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;
     }
→ Ответить