uvalive 6669 hidden tree(好壮圧dp)

タイトルはhereを参照
題意:シーケンスarr[]を与えて、そこからいくつかのサブシーケンスを選択して、サブシーケンスの値を左から右に順番にある二叉木の葉ノードに置いて、葉を除いて、すべてのノードの左右のサブツリー権と等しいようにします.サブツリーの重みと=サブツリーの葉の重みと.このような二叉木が存在する場合、選択されたサブシーケンスは合法的である.最も長い合法的なサブシーケンスはいくらですか.
考え方:
二叉木の可能な葉の最小重み(入手点)を列挙すると,明らかに,この数と共に二叉木を構成できる数は,この数と等しいか,この数の2^k倍である.このような関係を満たす数を,一つの集合と認識し,明らかに集合外の数は,集合内の数と二叉木を構成することはできない.では,すべての集合の最長男シーケンスを1つずつ求めるだけでよい.集合内のすべての数を最小重みで除算し、残りの数は1,2,4,8,16,32,64.....この2^kの数.左から右に行くと、最初の記入数が16で、2番目の記入数が16より大きくならないと、その16は合併できません.16が記入されている場合は32に合成されます.もちろん、16未満の数を記入してもいいです.では,2^kの数に対して,各数は,マージ中に必ず2つの状態しかなく,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
",ans);
    }
    return 0;
}