[TYVJ2340] 送礼物 - 双向搜索

题目限制

时间限制	内存限制	评测方式	题目来源
1000ms	131072KiB	标准比较器	Local

题目描述

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

输入格式

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

输出格式

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

提示

对于20%的数据 N<=26
对于40%的数据 W<=2^26

---

提交地址：joyoi

题解：

双向搜索， 先搜一半， 把那一半的所有拼出来的值放入数组t；

然后另一半，搜出一个值的时候在 t 中二分出<=w-now的最大的一个；

然后去更新ans；

数据太坑老是TLE；找不出原因

80分代码：

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 #define int long long

 inline int read()

 {

     int res=;bool fl=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')fl=;ch=getchar();}

     while(isdigit(ch)){res=(res<<)+(res<<)+(ch-'');ch=getchar();}

     return fl?-res:res;

 }

 int w, n;

 int a[];

 int t[], top;

 int ans;

 inline void dfs(int sum, int stp, int dep)

 {

     if (sum > w) return;

     if (stp > dep) {t[++top] = sum;return;}

     dfs(sum + a[stp], stp+, dep);

     dfs(sum, stp+, dep);

 }

 inline void dfs2(int sum, int stp, int dep)

 {

     if (sum > w) return;

     if (stp > dep)

     {

         int l = , r = top, mid;

         while (l < r)

         {

             mid = l + r +  >> ;

             if (t[mid] <= w - sum) l = mid;

             else r = mid - ;

         }

         int tmp = sum + t[l];

         if (tmp > w or tmp < ) return;

         ans = max(ans, sum + t[l]);

         return;

     }

     dfs2(sum + a[stp], stp+, dep);

     dfs2(sum, stp+, dep);

 }

 signed main()

 {

     w = read(), n = read();

     for (register int i =  ; i <= n ; i ++) a[i] = read();

     dfs(, , n / );

     sort(t + , t +  + top);

     dfs2(, n/+, n);

     cout << ans << endl;

     return ;

 }