「CH2401」送礼物解题报告

比眉伴天荒 2022-01-05 19:47 217阅读 0赞

# [CH2401 送礼物][CH2401] #

## 描述 ##

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

## 输入格式 ##

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

## 输出格式 ##

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

## 样例输入 ##

20 5
    7
    5
    4
    18
    1

## 样例输出 ##

## 数据范围与约定 ##

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

--------------------

# 思路 #

这么小的数据。。。一般是搜索吧？？？这么大的W，用DP做肯定不成，而且也不资瓷离散化。。。。

直接搜？+剪枝？我已经剪不下去了。。。不过80分勉勉强强还可以~

# 代码(搜索+剪枝) #

#include<bits/stdc++.h>
    using namespace std;
    #define LL long long
    #define MAXN 50
    
    int N;
    LL W, ans;
    LL G[MAXN], f[MAXN];//f表示“后缀和”
    
    bool cmp( LL x, LL y ){ return x > y; }
    
    void DFS( int x, LL h ){//x表示当前搜的是第x件物品，h表示已经取到的总重量
        while( x <= N && h + G[x] > W ) x++;//由于是降序排序，找到第一个还能继续搬的物品
        if ( x > N ){ ans = max( ans, h ); return; }//没东西了（或者没有可以搬的了），当然得回溯
        
        for ( ; x <= N; ++x ){
            if ( h + f[x] <= W ){ ans = max( ans, h + f[x] ); return; }//剪枝~ 后面都能拿，当然要都拿来最优啦~ 这个剪枝可以看做是最优化剪枝
            DFS( x + 1, h + G[x] );
        }
    }
    
    int main(){
        scanf( "%lld%d", &W, &N );
        for ( int i = 1; i <= N; ++i ) scanf( "%lld", &G[i] );
        sort( G + 1, G + N + 1, cmp );//剪枝~ 降序排序再搜~
        for ( int i = N; i >= 1; --i ) f[i] = f[i + 1] + G[i];
        
        DFS( 1, 0 );
        printf( "%lld\n", ans );
        return 0;
    }

相信大家都不会仅满足于80分~还有俩测试点呢。。。  
我们用一种神奇的搜索方式——双向搜索！

也就是说，先找前半段，预处理出所有可以达到的总重量，存在一个数组F中，然后再搜索后半段，对于后半段已取的质量，在F中二分找出既满足条件，又最大的重量，加起来更新ans的值就可以了。这样复杂度就为O(\\(2^\{\\frac n 2 \}+2^\{\\frac n 2 \} \\times \\log\_2n\\))基本可以满足要求。

# 代码 #

#include<bits/stdc++.h>
    using namespace std;
    #define LL long long
    #define MAXN 50
    
    int N, M;
    LL W, ans;
    LL G[MAXN];
    LL F[20000000], tot;
    
    bool cmp( LL x, LL y ){ return x > y; }
    
    void DFS_1( int x, LL h ){//第一次搜索，注意所有能得到的重量都要记录，所以不必剪枝 还有注意0也要记录
        F[++tot] = h;
        while( x <= M && h + G[x] > W ) x++;
        for ( ; x <= M; ++x ) DFS_1( x + 1, h + G[x] );
    }
    
    int EF( LL x ){//手打二分~
        int l(1), r(tot), mid, ans(1);
        while( l <= r ){
            mid = ( l + r ) >> 1;
            if ( F[mid] + x <= W ) l = mid + 1, ans = mid;
            else r = mid - 1;
        }
        return ans;
    }
    
    void DFS_2( int x, LL h ){
        ans = max( ans, h + F[EF(h)] );
        while( x <= N && h + G[x] > W ) x++;
        for ( ; x <= N; ++x ) DFS_2( x + 1, h + G[x] );
    }
    
    int main(){
        scanf( "%lld%d", &W, &N ); M = ( N >> 1 ) + 2;//lyd大佬说前半段1~N/2+2最快~蒟蒻当然照做
        for ( int i = 1; i <= N; ++i ) scanf( "%lld", &G[i] );
        sort( G + 1, G + N + 1, cmp );//照样排序
        
        DFS_1( 1, 0 );
        sort( F + 1, F + tot + 1 ); tot = unique( F + 1, F + tot + 1 ) - F - 1;//排序&去重
        DFS_2( M + 1, 0 );
        printf( "%lld\n", ans );
        return 0;
    }

搜索真是博大精深~

转载于:https://www.cnblogs.com/louhancheng/p/10099459.html

[CH2401]: http://contest-hunter.org:83/contest/0x20%E3%80%8C%E6%90%9C%E7%B4%A2%E3%80%8D%E4%BE%8B%E9%A2%98/2401%20%E9%80%81%E7%A4%BC%E7%89%A9