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速度要快一些。

#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;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
Tyvj Jan楼兰图腾 Tyvj Jan楼兰图腾
题意就是求出一个数左边比他大/小的数和右边比他大/小的数,用乘法原理计算出结果即可,可以类比树状数组解决逆序对的问题,对值域建立一个树状数组,倒序查询加入来得到右边,正序查询插入得到左边 #include<bits/stdc++.h
2019-07-05
下一篇 
P3469 BLO-Blockade P3469 BLO-Blockade
首先可以对第$i$个节点进行讨论 假如$i$不是割点(即把$i$和它有关的所有边都去除后图依然联通)那么这个图只有$i$是独立在外面的,由于求的是有序点对,所以除了$i$以外的$n-1$个点作为一个大的连通图对$i$加边,即为$2*(n-1
2019-07-05
  目录