Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 8:00 (UTC) due to technical maintenance. ×

ASHWANTH_K's blog

dp with bitmasking ideas needed.
By ASHWANTH_K, history, 12 days ago, In English

Is it possible to calculate the following recurrences in $$$O(N*2^N)$$$.

1) $$$dp[mask] = min(dp[mask] , dp[m_1] + dp[m_2]);$$$
where $$$m_1|m_2 = mask$$$

2) $$$dp[mask] = min(dp[mask] , dp[m_1] + dp[m_2]);$$$
where $$$m_1 \oplus m_2 = mask$$$ and $$$m_1$$$ ,$$$m_2$$$ are subsets of mask.

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ASHWANTH_K (previous revision, new revision, compare).

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't the second one the same as the first one?

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

First one is the same as Grouping ..

→ Reply