专栏文章

依然

大大海中的孤帆
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir2u27e
此快照首次捕获于
2025/12/04 14:50
3 个月前
此快照最后确认于
2025/12/04 14:50
3 个月前
查看原文

题干

题目描述

给定整数序列 AA ，要构造一个数列 BB ，其中 BB 由 0,10 ,1 组成，且 00 的个数等于 11 的个数。
在此前提下，构造一个数列 BB 使得 ∑i=2nA[i]∗(B[i]⊗B[⌊i/2⌋])\sum_{i=2}^n A[i]*(B[i] \otimes B[⌊i/2⌋])最大。输出这个值的最大可能值。
其中，⊗\otimes 表示同或运算。也就是，1⊗1=1,0⊗0=1,1⊗0=0,0⊗1=01 \otimes 1 = 1 , 0 \otimes 0 = 1 , 1 \otimes 0 = 0, 0 \otimes 1 = 0 。

输入格式

第一行输入一个正整数 nn 。
第二行输入 nn 个被空格分开的整数 A1,A2,…,AnA_1, A_2, \dots ,A_n 。

输出格式

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

样例

样例输入 1

CPP
6
14 10 -7 -50 -50 20

样例输出 1

CPP
20

样例解释 1

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

数据范围与提示

对于所有的测试点, 满足 nn 为偶数, n≤450,−109≤Ai≤109n \leq 450,-10^9 \leq A_i \leq 10^9
对于 10%10\% 的数据, 满足 n≤3n \leq 3
对于 30%30\% 的数据, 满足 n≤20n \leq 20
对于 80%80\% 的数据, 满足 n≤80n \leq 80

解题思路

第 ii 位答案在形成过程中与第 i∗2,i∗2+1i*2 , i*2+1 有关，可以近似看成一颗二叉树
我们假设 fu,i,j,opf_{u,i,j,op} 表示以 uu 为根的子树在集合一放了 ii 个, 集合二放了 jj 个, uu 在集合 opop 的最大贡献,枚举转移
但是如果这样做的话时间是 O(n4)O(n_{}^{4}) 的, 显然无法通过全部数据，怎么办呢？
考虑降维优化
我们发现，当集合一放的数确定时，集合二放的数也是可以推出来的。因此，转移数组便可以将一维， fu,i,opf_{u,i,op} 表示以 uu 为根的子树在集合一放了 ii 个， uu 在集合 opop 的最大贡献只需要记录集合一放的点数即可

code

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...