kyu_115s 2011-05-16 01:07:00
点我顶贴
收藏
删除
多维背包都会吧?不会就先做别的题目吧……
主要问题就是申请内存的问题吧。
题目里面有限制说所有限制上限乘起来最多5000000,所以dp数组就是个5000000的一维数组。做的时候,无论m是多少,都当做5来处理,只不过无用参数都是0就好了。然后写个函数,把五个维度的参数用一个函数处理成一个整型,这个整型理论上是不会超过5000000的,除非函数设计不合理。然后就可以把所有的状态对应到dp数组了。
这是叫hash函数吗?我对术语搞不清楚……
另外最好做些优化,比如把没用的限制全部清0,还有刚开始把函数的一些固定数值初始化。