Uva 1354 Mobile Computing

题目链接

题意：

　　在一个宽为r 的房间里，有s个砝码，每个天平的一端要么挂砝码，要么挂另一个天平，并且每个天平要保持平衡。

　　求使得所有砝码都放在天平上，且总宽度不超过房间宽度的最大值。

思路：

　　每个节点只能有两个子节点，这是一棵二叉树的形式。

　　通过枚举二叉树的形态，再枚举每一个叶子节点所放砝码，最后再计算每个方案的宽度并计算答案。

　　每增加一个天平，那么可以放砝码数 + 1。

note:

　　坑在0的输出了，用primtf("%.9lf\n", 0)输出来的是0 用0.0来输出才是0.000000 惨wa三发。

代码：

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <ctime>

 #include <set>

 #include <map>

 #include <list>

 #include <stack>

 #include <queue>

 #include <string>

 #include <vector>

 #include <fstream>

 #include <iterator>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define LL long long

 #define INF 0x3f3f3f3f

 #define MOD 1000000007

 #define eps 1e-5

 #define MAXN 110

 #define MAXM 100

 #define dd {cout<<"debug"<<endl;}

 #define pa {system("pause");}

 #define p(x) {cout<<x<<endl;}

 #define pd(x) {printf("%.7lf\n", x);}

 #define k(x) {printf("Case %d: ", ++x);}

 #define s(x) {scanf("%d", &x);}

 #define sd(x) {scanf("%lf", &x);}

 #define mes(x, d) {memset(x, d, sizeof(x));}

 #define do(i, x) for(i = 0; i < x; i ++)

 #define dod(i, x, l) for(i = x; i >= l; i --)

 #define doe(i, x) for(i = 1; i <= x; i ++)

 int n;

 double r, ans;

 double w[MAXN], v[MAXN];

 double ll[MAXN], rr[MAXN];

 bool vis[MAXN];

 int order[MAXN];

 void read()

 {

     scanf("%lf", &r);

     scanf("%d", &n);

     for (int i = ; i <= n; i ++)

         scanf("%lf", &w[i]);

 }

 void get_ans(int u)

 {

     memset(ll, , sizeof(ll));

     memset(rr, , sizeof(rr));

     memset(v, , sizeof(v));

     for (int i = u; i > ; i --)

     {

         if (order[i] == -)

         {

             int x = i * ;

             int y = i *  + ;

             v[i] = v[x] + v[y];

             double li = v[y] / v[i];

             double ri = v[x] / v[i];

             ll[i] = min(-li + ll[x], ri + ll[y]);

             rr[i] = max(-li + rr[x], ri + rr[y]);

         }

         else if (order[i])

         {

             v[i] = w[order[i]];

         }

     }

     double temp = rr[] - ll[];

     //printf("%.9lf\n", temp);

     if (temp - r < eps && temp > ans)

         ans = temp;

 }

 void dfs(int u, int num, int count)

 {

     //printf("%d %d %d\n", u, num, count);

     if (count == )

     {

         get_ans(u - );

         return ;

     }

     else if (order[u / ] != -)

     {

         dfs(u + , num, count);

     }

     else

     {

         if (count > num)

         {

             order[u] = -;

             dfs(u + , num + , count);

             order[u] = ;

         }

         if (num ==  && count > )

             return ;

         for (int i = ; i <= n; i ++)

             if (!vis[i])

             {

                 vis[i] = true;

                 order[u] = i;

                 dfs(u + , num - , count - );

                 order[u] = ;

                 vis[i] = false;

             }

     }

 }

 void solve()

 {

     memset(vis, false, sizeof(vis));

     memset(order, , sizeof(order));

     ans = -;

     if (n == ) printf("%.10lf\n", 0.0);

     else

     {

         order[] = -;

         dfs(, , n);

         printf(ans == -? "-1\n" : "%.10lf\n", ans);

     }

 }

 int main()

 {

     int T;

     scanf("%d", &T);

     while (T --)

     {

         read();

         solve();

     }

     return ;

 }

巴特西

Uva 1354 Mobile Computing

最新文章

热门文章