依然

· · 个人记录

题干

题目描述

给定整数序列 A ，要构造一个数列 B ，其中 B 由 0 ,1 组成，且 0 的个数等于 1 的个数。

在此前提下，构造一个数列 B 使得 \sum_{i=2}^n A[i]*(B[i] \otimes B[⌊i/2⌋]) 最大。输出这个值的最大可能值。

其中， \otimes 表示同或运算。也就是，1 \otimes 1 = 1 , 0 \otimes 0 = 1 , 1 \otimes 0 = 0, 0 \otimes 1 = 0 。

输入格式

第一行输入一个正整数 n 。

第二行输入 n 个被空格分开的整数 A_1, A_2, \dots ,A_n 。

输出格式

一行一个正整数，表示 \sum_{i=2}^n A[i]*(B[i] \otimes B[⌊i/2⌋]) 的最大可能值。

样例

样例输入 1

6
14 10 -7 -50 -50 20

样例输出 1

20

样例解释 1

最优的 B=\{0, 1, 1, 0, 0, 1\} 。

数据范围与提示

对于所有的测试点, 满足 n 为偶数, n \leq 450,-10^9 \leq A_i \leq 10^9

对于 10\% 的数据, 满足 n \leq 3

对于 30\% 的数据, 满足 n \leq 20

对于 80\% 的数据, 满足 n \leq 80

解题思路

第 i 位答案在形成过程中与第 i*2 , i*2+1 有关，可以近似看成一颗二叉树

我们假设 f_{u,i,j,op} 表示以 u 为根的子树在集合一放了 i 个, 集合二放了 j 个, u 在集合 op 的最大贡献,枚举转移

但是如果这样做的话时间是 O(n_{}^{4}) 的, 显然无法通过全部数据，怎么办呢？

考虑降维优化

我们发现，当集合一放的数确定时，集合二放的数也是可以推出来的。因此，转移数组便可以将一维， f_{u,i,op} 表示以 u 为根的子树在集合一放了 i 个， u 在集合 op 的最大贡献只需要记录集合一放的点数即可

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=505;
ll f[N][N];
inline void Max(ll &a,ll b){if(a<b)a=b;}
int d[N],n,sz[N];
void dfs(int u){
    memset(f[u],-0x1f,(n+1)<<3);
    sz[u]=1;
    if((u<<1)>n){f[u][1]=0;return;}
    else dfs((u<<1)),sz[u]+=sz[(u<<1)];
    if((u<<1|1)>n){
        for(int i=1;i<=sz[(u<<1)];++i){
            Max(f[u][i+1],f[(u<<1)][i]+d[(u<<1)]);
            Max(f[u][sz[(u<<1)]-i+1],f[(u<<1)][i]);
        }
    }else{
        dfs((u<<1|1));
        sz[u]+=sz[(u<<1|1)];
        for(int i=1;i<=sz[(u<<1)];++i){
            for(int j=1;j<=sz[(u<<1|1)];++j){
        Max(f[u][i+j+1],f[(u<<1)][i]+f[(u<<1|1)][j]+d[(u<<1)]+d[(u<<1|1)]);
        Max(f[u][sz[(u<<1)]-i+j+1],f[(u<<1)][i]+f[(u<<1|1)][j]+d[(u<<1|1)]);
        Max(f[u][sz[(u<<1|1)]-j+i+1],f[(u<<1)][i]+f[(u<<1|1)][j]+d[(u<<1)]);
        Max(f[u][sz[(u<<1)]-i+sz[(u<<1|1)]-j+1],f[(u<<1)][i]+f[(u<<1|1)][j]);
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    if(!n){puts("0");return 0;}
    for(int i=1;i<=n;++i)
        scanf("%d",&d[i]);
    dfs(1); 
    printf("%lld\n",f[1][n>>1]);
    return 0;
}