啊呜啊呜

因为F一直不会做,所以就水一篇E的blog吧

题目描述大概就是给你一个序列a,求$a_i + a_j$的最大值,其中$i|j\leq k$

一句话题解:高维前缀和子集取max

所以为了不让这篇blog过于单薄我就再写一下详细过程吧

设$f[s]$表示$i|j=s$的时候的答案。

显然对于$bit\&s>0$ ,$f[s-bit]$对$f[s]$有贡献。为了避免容斥当然用高维前缀和了,只不过这里我们维护一个最大值和次大值。每次更新的时候多判断一下就行了。

最近好颓qwq(

#include<bits/stdc++.h> 
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
#define N 1000005
#define M 4000005
int n, f[N][2], a[N], tmp[2];
inline void update (int s, int x)
{
    if (f[s][0] < x)
        f[s][1] = f[s][0], f[s][0] = x;
    else
    if (f[s][1] < x)
        f[s][1] = x;
}
int main ()
{
    scanf("%d", &n);
    int up = (1 << n) - 1;
    fo (i, 0, up) {scanf("%d", &a[i]); f[i][0] = a[i]; f[i][1] = -inf;}
    fo (i, 1, n)
    {
        fo (s, 1, up)
        {
            if (!(s & 1 << i - 1)) continue;
            int pre = s ^ 1 << i - 1;
            update(s, f[pre][0]);
            update(s, f[pre][1]);
        }
    }
    int ans = 0;
    fo (i, 1, up)
    {
        ans = std::max(ans, f[i][0] + f[i][1]);
        printf("%d\n", ans);
    }
    return 0;
}
分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *