TYVJ1340 送礼物

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%的数据 N<=26
对于40%的数据 W<=2^26
对于100%的数据 N<=45 W<=2^31-1

不想写题解。被各种卡。卡longlong，卡空间。。。

 #include <iostream>

 #include <cstdlib>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define min(a, b) ((a) < (b) ? (a) : (b))

 #define max(a, b) ((a) > (b) ? (a) : (b))

 inline void read(long long &x)

 {

     x = ;char ch = getchar(), c = ch;

     while(ch < ''|| ch > '')c = ch, ch = getchar();

     while(ch <= '' && ch >= '')x = x *  + ch - '', ch = getchar();

     if(c == '-')x = -x;

 }

 const int MAXN =  + ;

 long long W,n,g[MAXN],num1[( << ) + ],num2[( << ) + ],cnt1,cnt2,ans,mid;

 void dfs1(long long step, long long now)

 {

     if(now > W)return;

     if(step > mid)

     {

         if(now)num1[++cnt1] = now;

         return;

     }

     dfs1(step + , now + g[step]);

     dfs1(step + , now);

 }

 void dfs2(long long step, long long now)

 {

     if(now > W)return;

     if(step > n)

     {

         if(now)num2[++cnt2] = now;

         return;

     }

     dfs2(step + , now + g[step]);

     dfs2(step + , now);

 }

 int main()

 {

     read(W), read(n);

     mid = n/;

     for(register long long i = ;i <= n;++ i)

         read(g[i]);

     dfs1(, );

     std::sort(num1 + , num1 +  + cnt1);

     dfs2(mid + , );

     std::sort(num2 + , num2 +  + cnt2);

     ans = max(num1[cnt1], num2[cnt2]);

     long long l = ;

     for(register long long i = cnt2;i >= ;-- i)

     {

         while(num2[i] + num1[l] <= W && l <= cnt1)++ l;

         -- l;

         ans = max(ans, num2[i] + num1[l]);

     }

     printf("%lld", ans);

     return ;

 } 

TYVJ1340