CF888E Maximum Subsequence

首先我们看到数据范围$n\leq 35$加上每个数都可能取或不取,这样$2^{35}$的状态量自然是太大了,但对于这种取或不取实现一系列要求有个很常见的作法就是Meet-in-the-middle,也可以当成折半搜索,对于前一半选一些数,再对后一半选一些数,这样就只有$2^{\frac{35}{2}}$瞬间缩小了很多。

但一般这种搜索的瓶颈在于对两半数据合并统计状态,操作不当会导致增加$n^2$复杂度直接回归暴力做法,一般这也有些常用的套路,比如这题和poj1186方程的解数一样都是把两边的状态分别存在两个数组里,由于之前枚举时已经全膜过了,所以两个数组里的数都是$\leq m$的,这个性质很重要,我们可以靠它来贪心。

首先这两个数组抽任意两个数加起来都是$\leq 2m$,那么我们将两个数组不下降排序,对于抽出来$\geq m$的情况,显然两数组中最大的数加起来是最大的,膜m后对于$\geq m$情况只有它可能是最优解。

之后我们直接考虑加起来$\leq m$,我们可以建立两个指针$i j$一个指向h1数组开头一个指向h2末尾,若当前加起来$\geq m$我们便直接让$j$--,显然,因为h1是递增的,所以随着i的增大j只能减少才可能满足$\leq m$,这样并不会漏掉答案,这样扫过一边之后在与h1[p]+h2[q](两数组中最大的数加起来是最大的)取max,这样便是结果。

注意在搜索的时候可以向楼下的题解一样直接dfs,当然也可以和这个代码一样用二进制来枚举子集,比dfs速度要快一些。

 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
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000;
int n,m,a1[50],a2[50],p,q;
int h1[maxn],h2[maxn],num1=0,num2=0;
void calc()
{
    for(int i=0;i<(1<<p);i++)
    {
        int t=0;
        for(int j=1;j<=p;j++)
        if(i>>(j-1)&1) t=(t+a1[j])%m;
        h1[++num1]=t;
    }
    for(int i=0;i<(1<<q);i++)
    {
        int t=0;
        for(int j=1;j<=q;j++)
        if(i>>(j-1)&1) t=(t+a2[j])%m;
        h2[++num2]=t;
    }
    sort(h1+1,h1+1+num1);
    sort(h2+1,h2+1+num2);
    int i=1,j=num2;
    int ans=0;
    for(int i=1;i<=num1;i++)
    {
        while(h1[i]+h2[j]>=m&&j>0) j--;
        if(j<=0) break;
        ans=max(h1[i]+h2[j],ans);
    }
    ans=max(ans,h1[p]+h2[q]);
    printf("%d\n",ans);
}
int main()
{
    scanf("%d%d",&n,&m);
    p=n/2,q=n-p;
    for(int i=1;i<=p;i++) scanf("%d",&a1[i]);
    for(int i=1;i<=q;i++) scanf("%d",&a2[i]);
    calc();
    return 0;
}