P10484 题解

Melo.VVちゃん · 2024-07-19 18:56:24 · 题解

来一发双向搜索加双指针的题解。

题目大意

分析一下复杂度。

暴力搜索 \mathcal{O}(2^n) 明显会炸，但是 \mathcal{O}(2^{\frac{n}{2}+1}) 不会，所以双向搜索可行。

题目实现

劈成两半枚举所有可能的结果，每一半存入一个数组中。

最后从两个数组中分别拿出一个匹配，如果不超过 W，那么是一个可能的答案，统计最大值。

但是显然 \mathcal{O}(n^2) 的答案求解不可行，所以考虑食用双指针优化为 \mathcal {O}(n)。

我们将两个数组从大到小排序，显然对于第一个数组 a，随着下标不断增大，a_i 也不断增大，根据单调性，如果想要两个数的和维持在 \le W 的范围内，第二个数要不断缩小，所以我们可以再设一个指针 j 来倒序枚举第二个数组。

代码：

#include <bits/stdc++.h>
#define int long long
#define f(i ,m ,n ,x) for (int i = (m) ;i <= (n) ;i += (x))
using namespace std ;
template < typename T > inline void read (T &x) {
    x = 0 ;
    bool flag (0) ;
    register char ch = getchar () ;
    while (! isdigit (ch)) {
        flag = ch == '-' ;
        ch = getchar () ;
    }
    while (isdigit (ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48) ;
        ch = getchar () ;
    }
    flag ? x = -x : 0 ;
}
const int N = 50 ;
const int M = (1 << 23) + 7 ;
int w ,n ,g[N] ;
int v1[M] ,v2[M] ,tot1 ,tot2 ,mid ;
inline void dfs (int num ,int end ,int sum ,bool flag) {
    if (num == end + 1) {
        if (! flag) {
            v1[++ tot1] = sum ;
            return ;
        }
        v2[++ tot2] = sum ;
        return ;
    }
    dfs (num + 1 ,end ,sum ,flag) ;
    if (sum + g[num] <= w) {
        dfs (num + 1 ,end ,sum + g[num] ,flag) ;
    } // 第 num 个物品可以选或者不选
}
int ans ;
signed main () {
    read (w) ,read (n) ;
    f (i ,1 ,n ,1) {
        read (g[i]) ;
    }
    mid = n >> 1 ;
    dfs (1 ,mid ,0 ,0) ;
    dfs (mid + 1 ,n ,0 ,1) ;
    int j = tot2 ;
    sort (v1 + 1 ,v1 + tot1 + 1) ;
    sort (v2 + 1 ,v2 + tot2 + 1) ;
    f (i ,1 ,tot1 ,1) {
        while (j >= 1 && v2[j] + v1[i] > w) j -- ;
        ans = max (ans ,v2[j] + v1[i]) ;
    }
    cout << ans << '\n' ;
    return 0 ;
}