題意：
? ? ?給出房間的寬度r和每個吊墜的重量wi，設計一個盡量寬但寬度不能超過房間寬度的天平，掛著所有掛墜，每個天平的一段要么掛這一個吊墜，要么掛著另一個天平，每個天平的總長度是1，細節我給出題目中的幾個圖來方便理解：


思路：
? ? ? 敲了將近兩個小時，數據比較小，也就是說只要找到解決方法，一般就可以直接AC了，首先我們可以搜索枚舉天平的狀態，就是總的天平的框架的樣子，也就是二叉樹的樣子，這個地方卡了一會才想出來，我們可以直接枚舉當天天平上有的點，每一步搜索是在當前天平上已有的點的葉子節點中兩種決策，要么增加一個天平，要么不增加，在別的葉子節點上增加天平，總之當前這一步要在一個葉子節點上增加天平，（想想我們畫二叉樹的時候是不是這樣畫的），而且每增加一個天平就會在二叉樹上增加一個掛墜的數量，一直增加到測試數據給的吊墜的數量，對于每一個枚舉得到的二叉樹，我們可以知道他一定是n個葉子節點的二叉樹，然后我們用一個全排列（也可以寫深搜，用全排列是為了不讓代碼太多，太亂）給這個葉子附上對應的重量，賦完重量之后我們可以再用深搜來給每個非葉子節點到他做兒子和有兒子的距離求出來，這個比較簡單（不會可以直接看下面代碼），求完距離之后可以用深搜遍歷沒一條路徑，樹根的坐標是0，然后往左就-，往右就+得到一個最大和最小的坐標，然后根據坐標差來更新最優值，這個題目我寫了三個深搜，一個全排列AC的，感覺實現的有點麻煩，但不知道有沒有更省事的，目前百度不到，還有就是有一個比較坑人的地方就是當吊墜只有一個的時候直接輸出0，不是-1。




#include<stdio.h>
#include<string.h>
#include<algorithm>


#define N 3000


using namespace std;


typedef struct
{
? ?double ll ,rr ,ww;
? ?int mk;
}NODE;


NODE node[N];
int Now[N] ,n ,nn;
double num[10] ,r ,Ans;
double minn ,maxx;


double DFSlr(int now)
{
? ?if(node[now].mk) return node[now].ww;
? ?double lsum = DFSlr(now * 2);
? ?double rsum = DFSlr(now * 2 + 1);
? ?node[now].ll = rsum / (lsum + rsum);
? ?node[now].rr = lsum / (lsum + rsum);
? ?return lsum + rsum;
}


void DFSmm(double v ,int now)
{
? ?if(node[now].mk)
? ?{
? ? ? if(minn > v) minn = v;
? ? ? if(maxx < v) maxx = v;
? ? ? return;
? ?}
? ?DFSmm(v - node[now].ll ,now * 2);
? ?DFSmm(v + node[now].rr ,now * 2 + 1);
}




void DFS(int sw ,int sumnode)
{
? ?if(sw == n)
? ?{
? ? ? int tmpyz[10] ,nowid = 0;
? ? ? for(int i = 1 ;i <= sumnode ;i ++)
? ? ? if(node[Now[i]].mk) tmpyz[++nowid] = Now[i];
? ? ? for(int i = 1 ;i <= nn+1 ;i ++)
? ? ? {
? ? ? ? ?for(int j = 1 ;j <= n ;j ++)
? ? ? ? ?node[tmpyz[j]].ww = num[j];
? ? ? ? ?DFSlr(1);
? ? ? ? ?maxx = -100000 ,minn = 100000;
? ? ? ? ?DFSmm(0 ,1);
? ? ? ? ?if(maxx - minn <= r)
? ? ? ? ?{
? ? ? ? ? ? if(Ans < maxx - minn)
? ? ? ? ? ? Ans = maxx - minn;
? ? ? ? ?} ? ? ? ?
? ? ? ? ?next_permutation(num + 1 ,num + n + 1);
? ? ? ?}
? ? ? return;
? ?}
? ?for(int i = 1 ;i <= sumnode ;i ++)
? ?{
? ? ? if(node[Now[i]].mk)
? ? ? {
? ? ? ? node[Now[i]].mk = 0;
? ? ? ? node[Now[i]*2].mk = 1;
? ? ? ? node[Now[i]*2+1].mk = 1;
? ? ? ? Now[sumnode+1] = Now[i]*2;
? ? ? ? Now[sumnode+2] = Now[i]*2+1;
? ? ? ? DFS(sw + 1 ,sumnode + 2);
? ? ? ? node[Now[i]].mk = 1;
? ? ? ? node[Now[i]*2].mk = 0;
? ? ? ? node[Now[i]*2+1].mk = 0;
? ? ? }
? ?}
}


int main ()
{
? ?int t ,i;
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? scanf("%lf" ,&r);
? ? ? scanf("%d" ,&n);
? ? ? for(nn = i = 1 ;i <= n ;i ++)
? ? ? {
? ? ? ? ?scanf("%lf" ,&num[i]);?
? ? ? ? ?nn *= i;
? ? ? }
? ? ? if(n == 1)
? ? ? {
? ? ? ? ?printf("0\n");
? ? ? ? ?continue;
? ? ? }
? ? ? memset(node ,0 ,sizeof(node));
? ? ? Now[1] = 1 ,Ans = -1;
? ? ? node[1].mk = 1;
? ? ? DFS(1 ,1);
? ? ? printf("%.16lf\n" ,Ans);
? ?}
? ?return 0;
}
? ? ??
? ?
? ?
? ? ? ??
? ? ? ??
? ? ? ??
? ?
? ?
? ? ? ? ?
? ? ??

總結

以上是生活随笔為你收集整理的LA3403天平难题（4个DFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。