10012 How Big Is It?(****)

/*
题意：一堆小球，要求使用最小的矩形将它们全部装起来。
要求小球必须接地，至少与其他一个小球相邻
思路：涉及到状态转移，用到动态规划思想。原来通过深搜，剪枝结果WA，后来想到两个相邻小球半径相差很大的情况，于是没有了做题思路。看别人代码后，搜索中添加两个数组，A[i]表示第i个小球的半径大小，c[i]表示第i个小球排完后右边界最远的位置。于是有状态转移方程:  c[i]=max(c[j]+2*sqrt(A[j]*A[i])|j为第i个之间的小球)，最后需要检查一次左边界和右边界，可能出现左边界左移的情况，所以只要让c[i]都加上左移的距离即可！
*/

//错误代码：
#include <cstdio>
#include <cstring>
#include <cmath>
bool visit[10];
int T,n;
double radii[10];
double min;
int A[10],result[10];
void dfs(int now,int dep,double length)
{
	A[dep-1]=now;
	if(length>=min) return;
	if(dep==n)
	{
		if(length+radii[now]<min)
		{
			min=length+radii[now];
			memcpy(result,A,sizeof(A));
		}
	}
	for(int i=0;i<n;i++)
	{
		if(!visit[i])
		{
			visit[i]=1;
			dfs(i,dep+1,length+2*sqrt(radii[now]*radii[i]));
			visit[i]=0;
		}

	}
}
int main()
{
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%lf",&radii[i]);
		min=1e10;
		memset(visit,0,sizeof(visit));
		for(int i=0;i<n;i++)
		{
			visit[i]=1;
			dfs(i,1,radii[i]);
		}
		for(int i=0;i<n;i++)
			printf("%d ",result[i]);
		printf("\n");
		printf("%.3lf\n",min);
	}
	return 0;
}

//正解：
#include <cstdio>
#include <cmath>
#include <cstring>
double A[10],c[10];
double radii[10];
int n;
bool visit[10];
double ans;
void dfs(int cur)
{
	if(cur==n)
	{
		double move=0.0;
		for(int i=0;i<n;i++)
		{
			double temp=A[i]-c[i];
			if(temp>move)
				move=temp;
		}
		for(int i=0;i<n;i++)
			c[i]+=move;
		double res=0.0;
		for(int i=0;i<n;i++)
		{
			double temp=A[i]+c[i];
			if(temp>res)
				res=temp;
		}
		if(res<ans)
			ans=res;
		return;
	}
	for(int i=0;i<n;i++)
		if(!visit[i])
		{
			visit[i]=1;
			A[cur]=radii[i];
			c[cur]=0.0;
			for(int j=0;j<cur;j++)
			{
				double temp=c[j]+2*sqrt(A[cur]*A[j]);
				if(c[cur]<temp)
					c[cur]=temp;
			}
			dfs(cur+1);
			visit[i]=0;
		}
}
int main()
{
	freopen("data.in","r",stdin);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=0;i<n;i++)
			scanf("%lf",&radii[i]);
		memset(visit,0,sizeof(visit));
		ans=1e10;
		for(int i=0;i<n;i++)
		{
			A[0]=radii[i];
			c[0]=radii[i];
			visit[i]=1;
			dfs(1);
			visit[i]=0;
		}
		printf("%.3lf\n",ans);
	}
}