咏叹

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 2100000;

int T,n;
int a[45],top1,top2;
s64 Stk1[ONE],Stk2[ONE];
s64 Square, Ans, tot, RE;

int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    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 = 0;
    res = max(res,Get(A, B-A));
    res = max(res,Get(A/2,B));
    res = max(res,Get(B/2,A));
    return res;
}

void Dfs1(s64 val,int T)
{
    if(T>n/2) {Stk1[++top1] = val; return;}
    Dfs1(val,T+1);    Dfs1(val+a[T],T+1);
}

void Dfs2(s64 val,int T)
{
    if(T>n) {Stk2[++top2] = val; return;}
    Dfs2(val,T+1);    Dfs2(val+a[T],T+1);
}

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/2;
    double Temper = top2/3;
    while(Temper >= 1)
    {
        int A = Now + (int)Temper * (Random()*2.0-1);
        if(A<=0) A = (int)Temper * Random() + 1;
        s64 dE = Judge(A,id) - Judge(Now,id);
        if(dE > 0 || Random()<=exp(dE))
            Now = A;
        if(Temper > top2 / 2) Temper *= 0.1;
        Temper *= 0.75;
    }
    Judge(Now-1,id);    Judge(Now+1,id);
}

void Solve2()
{
    top1 = top2 = tot = 0;
    for(int i=1;i<=n;i++) a[i]=get(),a[i]*=2,tot += a[i];
    Dfs1(0,1);        sort(Stk1+1,Stk1+top1+1);    top1 = unique(Stk1+1,Stk1+top1+1)-Stk1-1;
    Dfs2(0,n/2+1);    sort(Stk2+1,Stk2+top2+1);    top2 = unique(Stk2+1,Stk2+top2+1)-Stk2-1;
    Ans = Square = 0;

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


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

void Dfs(s64 A,s64 B,int T)
{
    if(T>n)
    {
        Check(A,B);
        return;
    }
    Dfs(A+a[T],B,T+1);
    Dfs(A,B+a[T],T+1);
}

void Solve1()
{
    Ans = Square = 0;
    for(int i=1;i<=n;i++) a[i]=get(),a[i]*=2;
    Dfs(0,0,1);
    printf("%lld\n",Ans/2);
}

int main()
{
    srand(time(0));
    while(scanf("%d",&n)!=EOF)
    {
        if(n <= 25) Solve1();
        else Solve2();
    }
}