There is a mysterious planet called Yaen, whose space is 2-dimensional. There are many beautiful stones on the planet, and the Yaen people love to collect them. They bring the stones back home and make nice mobile arts of them to decorate their 2-dimensional living rooms.
In their 2-dimensional world, a mobile is defined recursively as follows:
For example, if you got three stones with weights 1, 1, and 2, here are some possible mobiles and their widths:
Given the weights of stones and the width of the room, your
task is to design the widest possible mobile satisfying both of the
following conditions.
You should ignore the widths of stones.
In
some cases two sub-mobiles hung from both ends of a rod might overlap
(see the figure on the right). Such mobiles are acceptable. The width of
the example is (1/3) + 1 + (1/4).
5 1.3 3 1 2 1 1.4 3 1 2 1 2.0 3 1 2 1 1.59 4 2 1 1 3 1.7143 4 1 2 3 5
-1 1.3333333333333335 1.6666666666666667 1.5833333333333335 1.7142857142857142
看到这题就一脸茫然……
把天平看成一棵二叉树……
然后枚举所有二叉树……
然后就更加茫然了
按照提示，选择两个节点合并成一棵新树。操作起来有点麻烦，但是可以使用多层vector，下一层先加入合并后的节点，然后加剩下的节点
比如
花了一下午，真的是服了
刚交上去uva就挂了
在poj上交的
不知道POJ的G++有多老……
没有bits/stdc++.h，printf用%lf会WA……
因为有spj，以后输出小数还是应该留长一点，不然可能会被卡（惨痛的Failed System Test教训）
AC代码
#include<cstdio>
#include<vector>
using namespace std;
#define REP(i,x,y) for(register int i=(x); i<(y); i++)
#define REPE(i,x,y) for(register int i=(x); i<=(y); i++)
#ifdef sahdsg
#define DBG(a,...) printf(a, ##__VA_ARGS__)
#else
#define DBG(a,...) (void)0
#endif
#define MAXN 10
double r;
int s;
struct node {
int i;
node *lc, *rc;
};
vector<node> V[MAXN];
int w[MAXN];
int calc(node *p, double&lm, double&rm) {
if(p->i==-1) {
int lw,rw;
double ll, lr, rl, rr;
lw=calc(p->lc,ll,lr);
rw=calc(p->rc,rl,rr);
if((~lw) && (~rw)) {
int a=rw+lw;
double ls=((double)rw)/a;
double rs=((double)lw)/a;
lm = max(ll+ls, rl-rs);
rm = max(rr+rs, lr-ls);
return lw+rw;
} else {
return -1;
}
}
lm=rm=0;
return w[p->i];
}
double ansl;
void dfs(int pos) {
if(pos==s-1) {
node &ro=V[pos][0];
double lm,rm;
if(~calc(&ro,lm,rm) && lm+rm<r) {
ansl=max(ansl,lm+rm);
}
return;
}
REP(i,0,V[pos].size()) REP(j,0,V[pos].size()) if(i!=j) {
V[pos+1].clear();
node k;
k.lc=&V[pos][i]; k.rc=&V[pos][j];
k.i=-1;
V[pos+1].push_back(k);swap(k.lc,k.rc);
REP(x,0,V[pos].size()) if(x!=i && x!=j) {
V[pos+1].push_back(V[pos][x]);
}
dfs(pos+1);
}
}
int main() {
#ifdef sahdsg
freopen("in.txt", "r", stdin);
#endif
int T;
scanf("%d", &T);
while(0<T--) {
scanf("%lf", &r);
scanf("%d", &s);
V[0].clear();
REP(_,0,s) {
scanf("%d", &w[_]);
V[0].push_back((node){_,NULL,NULL});
}
ansl=-1e9;
dfs(0);
if(ansl<-1) puts("-1");
else printf("%.15f\n", ansl);
}
return 0;
}
原文：https://www.cnblogs.com/sahdsg/p/10439575.html