题目链接：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枚举计算最大长度即可
早上再写吧。。。实在写不动了。。。。
记得还要看卡特兰数和康拓展开
