题目见

option=com_onlinejudge&Itemid=8&page=show_problem&problem=4681">here

题意：给一个序列arr[]，你从中选择一些子序列，将子序列的值从左往右依次放到某棵二叉树的叶子节点上，使得除了叶子，全部节点左右子树权和相等。子树的权和 = 子树叶子的权和。

假设存在这样一棵二叉树，选择的子序列就是合法的。问，最长的合法子序列是多少。

思路：

枚举二叉树可能的叶子的最小权(入手点)。显然，能和此数一起组成二叉树的数，要么和这个数相等。要么是这个数的2^k倍。把满足这样的关系的数。认做一个集合，显然集合外的数，不能和集合内的数组成二叉树。那么，我们仅仅须要一个一个得求出全部集合的最长子序列就可以。

把集合内的所有数所有除以最小权。剩下的数为1,2,4,8,16,32,64.....这样的2^k的数。如果你从左到右。第一个填的数为16，第二个填的数一定不会比16大，不然那个16无法合并。如果填的就是16，那就合成为32。当然，填小于16的数也是行的。

那么，对于2^k的数。每一个数，在合并过程中一定仅仅有两种状态。有1个，或者没有。

那么我们似乎就能够用状态压缩就可。

具体见代码：

#include<algorithm>

#include<iostream>

#include<string.h>

#include<stdio.h>

using namespace std;

const int INF=0x3f3f3f3f;

const int maxn=1010;

typedef long long ll;

bool base[maxn*505],vis[505],iss[maxn];

int arr[maxn],dp[maxn*505],brr[maxn],sum[maxn];

int solve(int x,int n)

{

    int i,j,lim,tp,ct=0,ans=0;

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

        if(arr[i]%x==0&&base[arr[i]/x])

            brr[++ct]=arr[i]/x;

    for(i=1;i<=ct;i++)

        sum[i]=sum[i-1]+brr[i];

    memset(dp,0xcf,sizeof dp);

    dp[0]=0;

    for(i=1;i<=ct;i++)

    {

        lim=2*brr[i];

        for(j=sum[i];j>=lim;j--)

        {

            tp=j-brr[i];

            if(!(tp&(brr[i]-1)))

                dp[j]=max(dp[j],dp[tp]+1);

        }

        dp[brr[i]]=max(dp[brr[i]],1);

    }

    for(i=1;i<=sum[ct];i++)

        if(base[i])

            ans=max(ans,dp[i]);

    return ans;

}

int main()

{

    int n,i,j,lim,ans;

    lim=500*maxn;

    for(i=1;i<lim;i<<=1)

        base[i]=true;

    while(scanf("%d",&n),n)

    {

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

            scanf("%d",&arr[i]);

        memset(vis,0,sizeof vis);

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

        {

            iss[i]=true;//是否叶子结点最小权值

            if(vis[arr[i]])

            {

                iss[i]=false;

                continue;

            }

            vis[arr[i]]=true;

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

            {

                if(j==i)

                    continue;

                if(arr[i]!=arr[j]&&arr[i]%arr[j]==0&&base[arr[i]/arr[j]])

                {

                    iss[i]=false;

                    break;

                }

            }

        }

        ans=0;

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

            if(iss[i])

                ans=max(ans,solve(arr[i],n));

        printf("%d\n",ans);

    }

    return 0;

}