随笔-20  评论-16  文章-36  trackbacks-0
1742 Coins
         传说中的楼教主出的题……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 古月残辉 阅读(231) 评论(0)  编辑 收藏 引用 所属分类: POJ

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


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 古月残辉