类背包问题

11 |

0 | 2009-7-26 22:25:14 | 显示全部楼层 |阅读模式

我怀疑这题是出自“0726 G4生日练习赛”，我今天刚好在做这个。我写了个dp的程序，不过我这程序既超时又超内存。官方的题解是：Gift的做法：把数组分成前后两半，分别计算前后两半的可取值（不会超时的，O(2^15)），把右边可取值排序（O(log(2^15)*2^15)=O(15*2^15)，再枚举左边的可取值，二分查找就可以了

使用道具举报

返回列表发新帖

千问

主题	0 回帖	4882万积分

论坛元老

Rank: 8 Rank: 8

积分: 48824836

加好友
发消息

回复楼主返回列表

问答

热门排行

1 开车不小心轻碰到一个女孩的脚，停车询问后开车离开，过后事主报警。
2 拆迁房未拿到产证，可以公证遗嘱吗？
3 试用期录用条件的约定
4 员工在非工作时间在公司宿舍意外死亡公司有没有责任
5 工资问题
6 关于欠条方面的
7 社保卡
8 出了交通事故多长时间能把车提出来
9 基本工资
10 讨债
11 《传唤通知书》什么时候会从网上消失?要等案件审判结束吗?
12 关于采暖费报销的问题
13 关于购买商场商铺后，然后直接出租给开发商，每月按购房款比例返租的问题
14 合同纠纷求帮助
15 婚姻法
16 财产纠纷
17 求助买假HTC手机不给退
18 公司9月7日新开张，一起工作的有10多人全部上了38天班。没有签劳动合同。9月满勤.国庆4.5日加班
19 房屋协议
20 未领结婚证
21 房东要收回店面
22 试用期离职
23 劳动合同到期终止公司是否需要支付代通知金
24 长江鼎立小额贷款有限公司骗了我朋友的钱要怎么样追回？
25 我怀疑遇到网络诈骗了
26 婚后女方父母出全资购买军产房给男女双方住，如以后涉及离婚，只凭两方自己签署的协议（条约）证明，不经公
27 工伤认定
28 租的房没到期房东把电给断了
29 拒绝加班被打旷工合理吗
30 辞职问题
31 电动车和出租车相撞，该如何陪付
32 【求救】子女财产继承问题?
33 偿还债务
34 我该怎么办
35 离婚案件咨询
36 北京博蓝慧想商贸有限公司笔业加工招商是真的吗？
37 1364409059 我要举报他QQ号
38 EMS发货到客户手里被掉包，现在不知道是物流问题还是客户问题，怎么办？
39 离婚诉讼费用计算
40 抚养归属
41 孩子抚养费以后可以再要么
42 婚外情
43 婚后男方出轨，想离婚怎么可以多拿财产
44 婚姻感情破裂、离婚
45 腾讯QQ空间页面游戏私下修改玩家道具属性
46 房产继承
47 我想查寻外地的企业的营业执照
48 合作外贸加工
49 个人与个人签订的劳务分包协议是否有效？是否受法律保护？
50 和情人在车上约会被警察抓住罚款4000元？没有发票。合法？
51 顾客弄坏东西让网管赔。。。
52 求助
53 我可以把堂弟户口迁跟我吗
54 交通事故十级伤残，赔偿标准是多少？
55 没登记有小孩要怎样解除关系呢
56 己婚怀孕孩子不是丈夫的！出生证明上可以不写男方资料吗？
57 谁有权力停水停电
58 不能理解的执行
59 辞职，老板要扣两个月工资
60 被人打了，自己用手挡和正当还击就定为打架，难道被打者只能挨打，不能正当防卫吗
61 工作
62 上海市男方上海的女方江西的！产假98天在社保拿了生育保险！那之后还有30天晚育假的工资由谁支付？
63 老人住院医疗费用怎么分
64 婚后女方父母首付，女方还贷，产权署名为夫妻两个人，怎样分割
65 我签了劳动合同之后发现对方可能是骗子，请问我怎样解除合同
66 求助求助！！！！
67 离婚房产
68 单位是否应该缴纳五险？
69 被人打了，不能正当防卫吗
70 行政诉讼
71 宜信普惠上海分中心
72 离婚财产分割
73 交通事故咨询（小汽车和自行车）
74 占用道路违规建房
75 在工地上摔伤该如何赔偿
76 劳动纠纷
77 单位一直没有签订合同也没有缴纳养老保险金，要求单位给补助。
78 殓葬费
79 购房问题咨询
80 房产继承权
81 武汉宏源馨实业有限公司抽奖活动是不是真的？
82 哺乳期女职工请一个月事假，工资怎么发
83 卡里钱被别人取走了2万元；银行有责任吗；卡并没有丢失过
84 合作加盟
85 对于网上谩骂
86 追债
87 工伤过了1年的仲裁时间可以直接起诉单位吗
88 离婚地皮归属
89 工伤鉴定与理赔
90 银行打印的工资明细可以做法庭上的收入证明吗？
91 请问网上被骗400元可以报警吗
92 摩托车撞电瓶车事故责如何认定？
93 农村自建房有土地使用证没有房产证能买么?
94 土地纠纷
95 公司因业绩考核掉，可以辞退员工吗
96 持有身份证号和银行帐号能做违法的事吗
97 农村房屋买卖成功但未过户，现办新房产证应该属哪方？
98 网上中奖诈骗怎么办？
99 大学农转非土地问题
100 放讹怎么办