题目见here

题意：给一个序列arr[]，你从中选择一些子序列，将子序列的值从左往右依次放到某棵二叉树的叶子节点上，使得除了叶子，所有节点左右子树权和相等。子树的权和 = 子树叶子的权和。如果存在这样一棵二叉树，选择的子序列就是合法的。问，最长的合法子序列是多少。

思路：

枚举二叉树可能的叶子的最小权(入手点)，显然，能和此数一起组成二叉树的数，要么和这个数相等，要么是这个数的2^k倍。把满足这种关系的数，认做一个集合，显然集合外的数，不能和集合内的数组成二叉树。那么，我们只需要一个一个得求出所有集合的最长子序列即可。
把集合内的所有数全部除以最小权，剩下的数为1,2,4,8,16,32,64.....这种2^k的数。假设你从左到右，第一个填的数为16，第二个填的数一定不会比16大，不然那个16无法合并。如果填的就是16，那就合成为32。当然，填小于16的数也是行的。那么，对于2^k的数，每个数，在合并过程中一定只有两种状态，有1个，或者没有。那么我们似乎就可以用状态压缩就可。

详细见代码：

#include
  
   
#include
   
     #include
    
      #include
     
       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