uva1354 回溯枚举二叉树

题目链接：https://cn.vjudge.net/problem/UVA-1354

比较朴素的算法就是使用dfs一一枚举出二叉树然后判断
问题是，这题的坑在于枚举二叉树之后还要进行计算
这玩意算起来有点麻烦，刚开始WA掉了几次，
又发现二叉树枚举出了问题...一个是扩充num节点的时候要判断是不是最后一个可填节点 是的话 后面继续dfs出来的东西会出现负的 sit=0 use>0 而且没办法进行扩充 可以说是很尴尬了...

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

int t[1001];
bool visit[11];
int T, s;
double right[1001], left[1001], value[1001], w[1001];
double ans, r;

int cnt = 0;
void judge(int num)                            //计算天平长度 
{
//  printf("%d\n", ++cnt);
    memset(value, 0, sizeof(value));
    memset(left, 0, sizeof(left));
    memset(right, 0, sizeof(right));                        //init
    for(int i=num; i>0; i--)                           //从后往前算 正常想法 
    {
        if(t[i]==-1)                                           //
        {
            int x = 2 * i;
            int y = 2 * i + 1;
            value[i] = value[x] + value[y];                         //计算悬挂点的重量                       
            double ll = value[y]/value[i];                          //计算悬挂点左右两侧长度 
            double rr = value[x]/value[i];          
            left[i] = min(left[x]-ll, rr+left[y]);                  //left < 0 表示 从悬挂点往左到最边上的距离 同理得right 
            right[i] = max(right[y]+rr, right[x]-ll);                  //计算左右两侧极值                 
        }
        else if(t[i])                               //节点i是挂东西的地方 计算重量 
        {
            value[i] = w[t[i]];
        }
    }
    double a = right[1] - left[1];
    //printf("%.10lf  %.10lf\n", a, a - r);
    if(a - r< 1e-5)
    {
        ans = max(ans, a);
        //printf("ans=  %.10lf\n",ans);
    }    
}
//使用数组t [1....num] 来模拟二叉树 根据二叉树的性质 如果parent = 节点 i 那么left child = 2*i right child = 2*i+1
// num : 当前正在枚举的位置 sit: 当前还剩下多少叶子节点可以填写  use: 当前还需要多少填写的内容 
// -1 表示 该节点为悬挂点 不可填写内容但儿子可以填写内容
//0 表示 该节点不填写任何内容 也就是不表示出来 作为终止
//n 表示把第n个物体填写在这个位置 
int dfs(int num, int sit, int use)               //num: 
{
    if(use==0 && sit==0)                        //dfs终止条件：
    {
        judge(num-1);       //计算天平长度 
        return 0;
    }
    if(t[num/2]!=-1)            //他的父亲不是悬挂点 他不能填 转向下一个节点 
    {
        dfs(num+1, sit, use);
    }
    else                                 
    { 
        //尝试扩充 num
        if(sit < use)                 //当前可以填写的位置不够 则尝试把当前节点作为悬挂点扩充 
        { 
            t[num] = -1;                              //标记当前节点为悬挂节点 
            dfs(num+1, sit+1, use);                    //dfs
            t[num] = 0;                                  //回溯 不这么尝试了 退回原来的状态 
        }
        //不尝试扩充 num 
        if(sit==1 && use>1)                          //如果当前可供填写的节点只有一个 且需要填写的节点多于1个  那么不扩充num的话 后面就没法填了 回退 
        {
            return 0;                           
        }    
        for(int i = 1; i <= s; i++)                 //尝试在num上填写各种东西 
        {
            if(!visit[i])                    //填写未填写的 
            {
                visit[i] = true;
                t[num] = i;                          //标记 
                dfs(num+1, sit-1, use-1);                //未使用 
                visit[i] = false;                   //回溯 
                t[num] = 0;
            }
        }
    }
    return 0; 
}
int main()
{

    scanf("%d", &T);
    while(T--)
    {
        memset(w, 0, sizeof(w));
        memset(t, 0, sizeof(t));
        memset(visit, false, sizeof(visit));
        scanf("%lf %d", &r, &s);
        for(int i = 1; i <= s; i++)
            scanf("%lf", &w[i]);
        t[1] = -1;
        ans = -1;
        if(s==1)
        {
            printf("%.16lf\n",0.0);
        }
        else
        {
            dfs(2, 2, s);
            if(ans==-1) printf("-1\n");
            else printf("%.16lf\n",ans);
        }
    }
    return 0;
}

然后我看了一下刘汝佳的题解。。。
完全不在一个频道上。。。他用二进制直接从1<<n-1开始枚举subnet
subnet = left|right
按位枚举 left ， right = subnet ^ left
用数组记录当前left right subnet的情况
然后不同情况最直接push进去 最后按size枚举计算最大长度即可
早上再写吧。。。实在写不动了。。。。
记得还要看卡特兰数和康拓展开