IOI 2015 — Boxes with Souvenirs

Правка en1, от protypuns, 2015-09-21 16:18:57

Hello guys :)

Today I tried to solve IOI 2015's first problem (Boxes with Souvenirs). I thought of dynamic programming:

dp[i] = min(dp[j] + min(l, 2 * (l - pos[j + 1]), 2 * pos[i]) ( j >= i — k and j < i)

So this algo is O(N^2) and it time limit. My question is how to reduce it to O(N).

Thanks in advance :)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский protypuns 2015-09-21 16:18:57 367 Initial revision (published)