╰( ̄▽ ̄)╭
每个非叶子节点,其左右子树叶子节点的权值之和相等。我们称这种二叉树叫平衡二叉树。
我们将一棵平衡二叉树叶子节点的权值从左到右列出来,假如这个权值序列是另一个序列A的子序列,我们称这棵平衡二叉树“隐藏”在序列A当中。在本题中,我们称一个序列S2是另一个序列S1的子序列,当且仅当S2可以由S1中删除0个或多个元素,但不改变S1中剩余元素的相对位置获得。
你的任务是对给定的整数序列,寻找当中隐藏的具有最多叶子节点的平衡二叉树。
n<=1000,1<=ai<=500
(⊙ ▽ ⊙)
显而易见,我们先枚举一个base,并将所有满足a[i]=base∗2j的提取出来,
形成一个新的数列A。 那么原问题就转化为:对于一个只有2的幂数的数列A,求一个最多叶子结点的隐藏平衡二叉树。容易想到,可以利用动态规划来做。
但问题在于如何写转移方程。如果我们摒弃时间复杂度不谈,
设f[i][j]表示前i个数中,未合并的数之和为j,的最多合并次数。 显然f[i−1][j]+1⇒f[i][j+A[i]] (A[i]<=lowbit(j))先明白lowbit()的意义。
lowbit(x)表示x的二进制中,只保留最低位的1及其后面的0,得到的数。由于A[i]<=lowbit(j),理解为,A[i]可以暂时储存在j中,因此可以转移。
如果不满足A[i]<=lowbit(j),会导致不连续的合并,是不允许的。f[i][j]的第一维可以滚动;
第二维,可以只枚举可以达到的和的最大值。这样优化之后,可以勉强卡过。
( ̄~ ̄)
#include#include #include #include #include #define ll long longusing namespace std;const char* fin="tree.in";const char* fout="tree.out";const int inf=0x7fffffff;const int maxn=1007,maxa=507,maxk=300000;int n,i,j,k,ans=1;int a[maxn];int b[maxn],mi[maxn];int f[maxk];bool bz[maxa];void solve(){ int i,j,k,l,MAX=0; f[0]=0; for (i=1;i<=b[0];i++){ for (j=MAX;j>=0;j--){ if (j==0 || (j&-j)>=b[i]){ k=j+b[i]; if (k>=maxk) continue; f[k]=max(f[k],f[j]+1); if ((k&-k)==k) ans=max(ans,f[k]); MAX=max(MAX,k); } } }}int main(){ freopen(fin,"r",stdin); freopen(fout,"w",stdout); scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d",&a[i]); //for (i=1,j=0;i<1< <<=1,j++) po[i]=j; for (i=1;i
(⊙v⊙)
关键点:
1.把原数列中提取出一个新的数列。 通过枚举,来简化问题。 2.运用特殊的DP技巧 本题的具体操作是,发现了题目中的特殊性。