随笔-20  评论-16  文章-36  trackbacks-0
         传说中的楼教主出的题……TLE到无语……
         开始时是想到一道做过的DP,很自然的从后往前推,O(mnmax(ci))结果TLE,优化下,每次取最小上界,还是TLE……最后都有点怀疑是哪个地方卡住没运行下去了……找不到测试数据,找了个别人写的程序,看了下,比我少重for,速度快不少,主要思想就是记录每个数能不能,如果能最少可以由几个Ai得到(在已经使用完A1~Ai-1的情况下)下面是主要的代码:
         
            for( j= coins[i].val; j<= upper; j++ ){
                
if!flag[j] && flag[j-coins[i].val] && curCount[j-coins[i].val]<coins[i].count ){
                    flag[j]
= 1;
                    _count
++;
                    curCount[j]
= curCount[j-coins[i].val]+1;
                }

            }

posted on 2009-04-02 21:05 古月残辉 阅读(233) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理