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

ZOJ 3215
Автор Shinta, 13 лет назад, По-английски
Can anyone help me with this problem http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3215 ?

If N = n * m, an obvious O(N^2 * k) dp solution won't fit in time. Besides, there is no nice and easy-to-notice proprierty like unimodality of some involved calculations, etc. So it's kind of difficult.

Help? ^^
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I think you should to optimize your solution. Do not use recursive dp. My solution has the same complexity, but works very fast.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Could you explain what does the "unimodality of some involved calculation" mean ?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
There exists a Knuth Optimization like(for optimal binary tree problem) trick for this problem which I could find by guessing. Guess some relations for the "loop bounds" and verify them. If you need more hints, please tell.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
I have just solved the problem using Knuth Optimization, it was very nice! thanks :)
→ Ответить