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

COUNT — Another Very Easy Problem! WOW!!! SPOJ
Автор jugal_sahu, 11 лет назад, По-английски

I was trying to solve COUNT(spoj problem).I am able to solve it using 3D DP but it will give segmentation fault because of the constraints.Can anyone help?

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

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Always post the link to the problem when you ask for help.

Solution:

dp[n][k] -- the answer.

One can fix the number of ones in final partition:

0 ones -- dp[n - k][k] ways,

1 one -- dp[n - k][k - 1] ways,

...

n ones -- dp[n - k][0] ways.

So dp[n][k] = .

→ Ответить
»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How is it different from P(n,k), partitioning ‘n’ elements in ‘k’ sets?

→ Ответить