首页 > 代码库 > 【Foreign】咏叹 [模拟退火]
【Foreign】咏叹 [模拟退火]
咏叹
Time Limit: 100 Sec Memory Limit: 256 MBDescription
有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组。
Source
首先，必然是全部木棍都用上的时候最优，对于n=2的时候，显然就是分三种情况讨论一下就好了。
然后我们从n=2的情况拓展。发现，其实可以把多个木棍并在一起，使其变为n=2的情况，然后讨论。那么现在答案只和两段的长度有关了。
但是直接暴力搜索是O(2^40)的，显然不行，我们考虑分为两部分来搜索，搜索前n/2个，和后n/2个，表示选不选得到的价值，现在效率是O(2*2^20)。
然后怎么得到答案呢？显然：如果我们设宽为x，则长为tot-2x(tot为总长)，那么这是一个二次函数，必然有峰值。
所以我们大胆猜测，我们确定了一半，另外一半使得其答案最优的话也可能满足有峰值的性质。
然后我们固定一半，另一半运用模拟退火求解即可！
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<ctime> 9 using namespace std; 10 typedef long long s64; 11 12 const int ONE = 2100000; 13 14 int T,n; 15 int a[45],top1,top2; 16 s64 Stk1[ONE],Stk2[ONE]; 17 s64 Square, Ans, tot, RE; 18 19 int get() 20 { 21 int res=1,Q=1; char c; 22 while( (c=getchar())<48 || c>57) 23 if(c==‘-‘)Q=-1; 24 if(Q) res=c-48; 25 while((c=getchar())>=48 && c<=57) 26 res=res*10+c-48; 27 return res*Q; 28 } 29 30 s64 Get(s64 width,s64 length) 31 { 32 s64 res = length * width; 33 34 if(res > Square || (res==Square && length>Ans)) 35 Square = res, Ans = length; 36 return res; 37 } 38 39 s64 Check(s64 A,s64 B) 40 { 41 if(A > B) swap(A,B); 42 s64 res = 0; 43 res = max(res,Get(A, B-A)); 44 res = max(res,Get(A/2,B)); 45 res = max(res,Get(B/2,A)); 46 return res; 47 } 48 49 void Dfs1(s64 val,int T) 50 { 51 if(T>n/2) {Stk1[++top1] = val; return;} 52 Dfs1(val,T+1); Dfs1(val+a[T],T+1); 53 } 54 55 void Dfs2(s64 val,int T) 56 { 57 if(T>n) {Stk2[++top2] = val; return;} 58 Dfs2(val,T+1); Dfs2(val+a[T],T+1); 59 } 60 61 s64 Judge(int i,int j) 62 { 63 return Check(Stk1[j] + Stk2[i],tot - Stk1[j] -Stk2[i]); 64 } 65 66 double Random() {return (double)rand()/RAND_MAX;} 67 void Deal(int id) 68 { 69 int Now = top2/2; 70 double Temper = top2/3; 71 while(Temper >= 1) 72 { 73 int A = Now + (int)Temper * (Random()*2.0-1); 74 if(A<=0) A = (int)Temper * Random() + 1; 75 s64 dE = Judge(A,id) - Judge(Now,id); 76 if(dE > 0 || Random()<=exp(dE)) 77 Now = A; 78 if(Temper > top2 / 2) Temper *= 0.1; 79 Temper *= 0.75; 80 } 81 Judge(Now-1,id); Judge(Now+1,id); 82 } 83 84 void Solve2() 85 { 86 top1 = top2 = tot = 0; 87 for(int i=1;i<=n;i++) a[i]=get(),a[i]*=2,tot += a[i]; 88 Dfs1(0,1); sort(Stk1+1,Stk1+top1+1); top1 = unique(Stk1+1,Stk1+top1+1)-Stk1-1; 89 Dfs2(0,n/2+1); sort(Stk2+1,Stk2+top2+1); top2 = unique(Stk2+1,Stk2+top2+1)-Stk2-1; 90 Ans = Square = 0; 91 92 for(int i=1;i<=top1;i++) 93 Deal(i); 94 95 96 printf("%lld\n",Ans/2); 97 } 98 99 void Dfs(s64 A,s64 B,int T)100 {101 if(T>n)102 {103 Check(A,B);104 return;105 }106 Dfs(A+a[T],B,T+1);107 Dfs(A,B+a[T],T+1);108 }109 110 void Solve1()111 {112 Ans = Square = 0;113 for(int i=1;i<=n;i++) a[i]=get(),a[i]*=2;114 Dfs(0,0,1);115 printf("%lld\n",Ans/2);116 }117 118 int main()119 {120 srand(time(0));121 while(scanf("%d",&n)!=EOF)122 {123 if(n <= 25) Solve1();124 else Solve2(); 125 }126 }
【Foreign】咏叹 [模拟退火]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。