【Foreign】咏叹 [模拟退火]

咏叹

Time Limit: 100 Sec Memory Limit: 256 MB

Description

　　有n根木棍，第i根长度为ai。你要贴着墙围出一个矩形区域，木棍围成的矩形边缘必须平行或垂直于墙，且又一边必须利用墙。你可以把至多1根木棍劈成两根(不一定要在整数位置)。最大化矩形面积。

Input

　　包含多组数据。每组数据第一行一个整数n，第二行n个整数ai。

Output

　　输出面积最大的矩形与墙壁平行的那条边的长度(显然是一个整数)，若有多个最优解输出与墙壁平行的那条边最长的。

Sample Input

3
   3 3 3
   4
   4 4 4 4

Sample Output

　　6
　　8

HINT

　　对于10%的数据，n=2。
　　对于30%的数据，n<=15。
　　对于50%的数据，n<=32。
　　对于另外20%的数据，ai<=100。
　　对于100%的数据，2<=n<=40，1<=ai<=10^9，数据不超过10组。

Solution

　　首先，必然是全部木棍都用上的时候最优，对于n=2的时候，显然就是分三种情况讨论一下就好了。

　　然后我们从n=2的情况拓展。发现，其实可以把多个木棍并在一起，使其变为n=2的情况，然后讨论。那么现在答案只和两段的长度有关了。

　　但是直接暴力搜索是O(2^40)的，显然不行，我们考虑分为两部分来搜索，搜索前n/2个，和后n/2个，表示选不选得到的价值，现在效率是O(2*2^20)。

　　然后怎么得到答案呢？显然：如果我们设宽为x，则长为tot-2x(tot为总长)，那么这是一个二次函数，必然有峰值。

　　所以我们大胆猜测，我们确定了一半，另外一半使得其答案最优的话也可能满足有峰值的性质。

　　然后我们固定一半，另一半运用模拟退火求解即可！

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<ctime>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 int T,n;

 int a[],top1,top2;

 s64 Stk1[ONE],Stk2[ONE];

 s64 Square, Ans, tot, RE;

 int get()

 {

         int res=,Q=;  char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 s64 Get(s64 width,s64 length)

 {

         s64 res = length * width;

         if(res > Square || (res==Square && length>Ans))

             Square = res, Ans = length;

         return res;

 }

 s64 Check(s64 A,s64 B)

 {

         if(A > B) swap(A,B);

         s64 res = ;

         res = max(res,Get(A, B-A));

         res = max(res,Get(A/,B));

         res = max(res,Get(B/,A));

         return res;

 }

 void Dfs1(s64 val,int T)

 {

         if(T>n/) {Stk1[++top1] = val; return;}

         Dfs1(val,T+);    Dfs1(val+a[T],T+);

 }

 void Dfs2(s64 val,int T)

 {

         if(T>n) {Stk2[++top2] = val; return;}

         Dfs2(val,T+);    Dfs2(val+a[T],T+);

 }

 s64 Judge(int i,int j)

 {

         return Check(Stk1[j] + Stk2[i],tot - Stk1[j] -Stk2[i]);

 }

 double Random() {return (double)rand()/RAND_MAX;}

 void Deal(int id)

 {

         int Now = top2/;

         double Temper = top2/;

         while(Temper >= )

         {

             int A = Now + (int)Temper * (Random()*2.0-);

             if(A<=) A = (int)Temper * Random() + ;

             s64 dE = Judge(A,id) - Judge(Now,id);

             if(dE >  || Random()<=exp(dE))

                 Now = A;

             if(Temper > top2 / ) Temper *= 0.1;

             Temper *= 0.75;

         }

         Judge(Now-,id);    Judge(Now+,id);

 }

 void Solve2()

 {

         top1 = top2 = tot = ;

         for(int i=;i<=n;i++) a[i]=get(),a[i]*=,tot += a[i];

         Dfs1(,);        sort(Stk1+,Stk1+top1+);    top1 = unique(Stk1+,Stk1+top1+)-Stk1-;

         Dfs2(,n/+);    sort(Stk2+,Stk2+top2+);    top2 = unique(Stk2+,Stk2+top2+)-Stk2-;

         Ans = Square = ;

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

             Deal(i);

         printf("%lld\n",Ans/);

 }

 void Dfs(s64 A,s64 B,int T)

 {

         if(T>n)

         {

             Check(A,B);

             return;

         }

         Dfs(A+a[T],B,T+);

         Dfs(A,B+a[T],T+);

 }

 void Solve1()

 {

         Ans = Square = ;

         for(int i=;i<=n;i++) a[i]=get(),a[i]*=;

         Dfs(,,);

         printf("%lld\n",Ans/);

 }

 int main()

 {

         srand(time());

         while(scanf("%d",&n)!=EOF)

         {

             if(n <= ) Solve1();

             else Solve2();

         }

 }

巴特西