Shinta's blog

ZOJ 3215
By Shinta, 13 years ago, In English
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? ^^
  • Vote: I like it
  • +5
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
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.
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
I have just solved the problem using Knuth Optimization, it was very nice! thanks :)
→ Reply