╰(￣▽￣)╭

每个非叶子节点，其左右子树叶子节点的权值之和相等。我们称这种二叉树叫平衡二叉树。

我们将一棵平衡二叉树叶子节点的权值从左到右列出来，假如这个权值序列是另一个序列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<iostream>

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<math.h>

#define ll long long

using 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<<maxk;i<<=1,j++) po[i]=j;

    for (i=1;i<maxa;i++){

        memset(bz,0,sizeof(bz));

        memset(mi,0,sizeof(mi));

        memset(f,128,sizeof(f));

        for (j=i,k=0;j<maxa;j=j*2){

            bz[j]=true;

            mi[j]=++k;

        }

        b[0]=0;

        for (j=1;j<=n;j++)

            if (bz[a[j]]) b[++b[0]]=a[j]/i;

        if (b[0]) solve();

    }

    printf("%d",ans);

    return 0;

}

(⊙v⊙)

关键点：

1.把原数列中提取出一个新的数列。

通过枚举，来简化问题。

2.运用特殊的DP技巧

本题的具体操作是，发现了题目中的特殊性。