P1340 送礼物

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

作为惩罚，GY被遣送去帮助某神牛给女生送礼物(GY：貌似是个好差事)但是在GY看到礼物之后，他就不这么认为了。某神牛有N个礼物，且异常沉重，但是GY的力气也异常的大(-_-b)，他一次可以搬动重量和在w(w<=2^31-1)以下的任意多个物品。GY希望一次搬掉尽量重的一些物品，请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。

输入格式

第一行两个整数，分别代表W和N。
以后N行，每行一个正整数表示G[i],G[i]<= 2^31-1。

输出格式

仅一个整数，表示GY在他的力气范围内一次性能搬动的最大重量。

测试样例1

输入

20 5
7
5
4
18
1

输出

19

备注

对于20%的数据 N<=26
对于40%的数据 W<=2^26
对于100%的数据 N<=45 W<=2^31-1

折半DFS。先DFS前一半物品，枚举每个物品拿或不拿，再DFS后一半物品，与之前算到的结果匹配。

堆了各种细节优化，还是有一个点1200ms……

最后加了个玄学卡时优化，过了。总计提交7次，中间评测机抽风3次，这题神TM鬼畜。

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #define LL long long
 8 #define HK_Reporter main
 9 using namespace std;
10 const int mxn=60;
11 LL read(){
12     LL x=0,f=1; char ch=getchar();
13     while(ch<'0' || ch>'9')ch=getchar();
14     if(ch=='-'){f=-1;ch=getchar();}
15     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 int n;
19 LL w;
20 LL a[mxn];
21 LL res[5000000],cnt;
22 int find(LL x){
23     int l=1,r=cnt;
24     int mid;
25     while(l<=r){
26         mid=(l+r)>>1;
27         if(res[mid]<x)l=mid+1;
28         else if(res[mid]>x) r=mid-1;
29     }
30     return l-1;
31 }
32 LL ans=0;int mid;
33 int bignews=0;
34 void dfs(int now,int limit,LL wt){
35     bignews++;
36     if(bignews>10000000){
37         printf("%lld
",ans);
38         exit(0);
39     }
40     if(now>limit){
41         if(limit==mid){
42             res[++cnt]=wt;
43             return;
44         }
45         int tmp=find(w-wt);
46         ans=max(ans,wt+res[tmp]);
47         return;
48     }
49     dfs(now+1,limit,wt);//不选
50     if(wt+a[now]<=w)dfs(now+1,limit,wt+a[now]);//选 
51     return;
52 }
53 int HK_Reporter(){
54     w=read();n=read();
55     int i,j;
56     for(i=1;i<=n;i++){
57         a[i]=read();
58     }
59     mid=n/2;
60     dfs(1,mid,0);
61     sort(res+1,res+cnt+1);
62     dfs(mid+1,n,0);
63     printf("%lld
",ans);
64     return 0;
65 }