Codeforces 888E

888E - Maximum Subsequence

题意

给出一些数字，现在选择 (k) 个不同的下标对应的数字，问它们的和模 (m) 最大为多少？

分析

用到了 meet-in-the-middle 的思想，能极大的优化 DFS 的暴力。
数字的个数 (n) 只有 (35)，但直接暴力 (2^{35}) 显然不行。
我们可以分别暴力左右 (frac{n}{2}) 个数，分别丢到两个 (set) 中，遍历第一个 (set) ，二分查找第二个 (set) 。
复杂度：(O(2^{frac{n}{2}}log(2^{frac{n}{2}}))) 也就是 (O(frac{n}{2}*2^{frac{n}{2}}))。

code

#include<bits/stdc++.h>
using namespace std;
int n, m, a[44];
set<int> st[2];
void dfs(int s, int l, int r) {
    if(l == r) {
        st[r == n].insert(s);
        return;
    }
    dfs((s + a[l]) % m, l + 1, r);
    dfs(s, l + 1, r);
}
int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    dfs(0, 0, n / 2);
    dfs(0, n / 2, n);
    st[0].insert(0);
    st[1].insert(0);
    int ans = 0;
    for(int i : st[0]) {
        int x = m - i - 1;
        auto it = st[1].upper_bound(x);
        it--;
        ans = max(ans, *it + i);
    }
    cout << ans << endl;
    return 0;
}