[动态规划] pku3375 二维DP优化
评论34次阅读2007.09.11 22:28; 作者：Felicia
是POJ月赛的题目，以下是官方解题报告
A O(NM) dynamic programming algorithm is quite apparent after sorting the computers and network interfaces by their coordinates. Furthermore, in any optimized case, for each computer the difference between the the indices of the network interfaces matching to and closest to the computer is never larger than N. So the complexity could be reduced to O(N2)
有很多细节不好考虑，应该是我的水平原因。最后我向updog要了数据才过的。而且代码写的不好。将就看一下吧。
发表回复
- 评论 (0)
- 引用通告 (0)
发表评论 引用通告暂无评论.
暂无引用通告