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

ZOJ 3215
Автор Shinta, 15 лет назад, По-английски
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
  • Проголосовать: не нравится

15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
I think you should to optimize your solution. Do not use recursive dp. My solution has the same complexity, but works very fast.
→ Ответить
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
Could you explain what does the "unimodality of some involved calculation" mean ?
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +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.
→ Ответить
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
I have just solved the problem using Knuth Optimization, it was very nice! thanks :)
→ Ответить