DDOSvoid's Blog

CF 888E Maximum Subsequence

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目描述

http://codeforces.com/problemset/problem/888/E

Solution

我们考虑 $meet~in~the~middle$，得到两个数组之后排序

首先两边的和最大为 $2m-2$，所以对于大于等于 $m$ 的最大值只有可能是两个数组的最大值之和

剩下的小于 $m$ 的最大值我们可以直接 $two~ pointer$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 40
#define maxm 1000010
using namespace std;

int n, p, m, a[maxn], b[maxn];

int u[maxm], v[maxm], c1, c2;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n >> p; m = n / 2;
    for (int i = 1; i <= m; ++i) cin >> a[i];
    for (int i = m + 1; i <= n; ++i) cin >> b[i - m]; n = n - m;
    for (int i = 0; i < (1 << m); ++i) {
        int sum = 0;
        for (int j = 1; j <= m; ++j) 
            if (i >> j - 1 & 1) sum = (sum + a[j]) % p; 
        u[++c1] = sum;
    }
    for (int i = 0; i < (1 << n); ++i) {
        int sum = 0;
        for (int j = 1; j <= n; ++j)
            if (i >> j - 1 & 1) sum = (sum + b[j]) % p;
        v[++c2] = sum; 
    }
    sort(u + 1, u + c1 + 1); sort(v + 1, v + c2 + 1);
    int j = c2, ans = (u[c1] + v[c2]) % p;
    for (int i = 1; i <= c1; ++i) {
        while (j && u[i] + v[j] >= p) --j;
        ans = max(ans, u[i] + v[j]);
    } cout << ans << "\n";
    return 0;
}