Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Re:N^2的状态表示不可能通过10万的数据吧。内存也开不了。必须降维啊，难道是二分加判断吗。

Posted by tasty at 2014-07-25 14:34:49 on Problem 3351 and last updated at 2014-07-25 14:35:28
In Reply To:N^2的状态表示不可能通过10万的数据吧。内存也开不了。必须降维啊，难道是二分加判断吗。 Posted by:yygy at 2014-07-25 14:29:09

我开始的想法是贪心，但是贪心貌似得不到精确的解(或者说没有找到得到精确解的
贪心方法)，贪心只能估算出某个状态的下界和上界(类似估价函数)，利用上界来更
新答案，以这个答案为标准，凡是  某个状态的代价+到终点的下届>=ans就剪枝。。。


这个方法需要很好的估价函数作为基础(尤其是下界估价)

Followed by:

Post your reply here: