题目描述
万众瞩目的《跨时代》专辑发行之后，周杰伦又开始了他的世界巡回演唱会《超时代》。小鸿是周董的铁杆粉丝，这种机会她当然不愿错过，她认为电视机前哪怕1nm的距离与在现场1km的距离相比都差多了，这是两种截然不同的感觉。所以小鸿就计划着带小y去看周杰伦的演唱会。

小鸿到达现场后碰巧赶上演唱会布置道具，而为了布置道具自然要有一个空地，而且还得是矩形的。演唱会主办方临时跟消防局借了n个栏杆，想要用这n个栏杆围出一个尽量大的矩形以满足粉丝们的各种要求，然而麻烦的是这些栏杆长度不一，给围场地带来了一定难度。

身为神犇的小鸿对于这种问题自然觉得是小case，她用自己的脑子就能算出最大面积。可是很不幸她第一次来到周董的演唱会，激动得脑子断了路，所以小y向你求救：

请你来编写一个程序，计算用这n个栏杆所能围成矩形的最大面积。（注：必须要刚好围成一个矩形，即不能出现多余的边长，且不能切断栏杆，但所给栏杆不一定要全部用上）。

输入
第一行一个正整数n，表示栏杆的数量。
第二行n个正整数，表示每根栏杆的长度li。
输出
仅一行一个正整数，表示用给出的栏杆围成最大矩形的面积。如果不能围成矩形，输出”No Solution”（不包含引号，严格区分大小写与空格）。
样例输入
4
1 1 1 1
样例输出
1
提示
样例输入2：

4

1 1 1 2

样例输出2：

No Solution

【数据规模和约定】

对于20%的数据：li全部相等。

对于60%的数据，1<=n<=10。

对于100%的数据，1<=n<=16,1<=li<=15。

题解
n<=16，显然状压，枚举一个集合N，用背包判断是否能够组成长度相等的两段，最后枚举两个互异集合找最大值就好了。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
int f[2000],g[1<<17],n,len[20],ans;
using namespace std;
inline int read()
{int x=0;char ch=getchar();while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x;
}
void dp(int sum,int now)
{if (sum&1) return;memset(f,0,sizeof(f));f[0]=1;for (int i=0;i<n;i++){if (now&1<<i){for (int j=sum;j>=len[i];j--){if (f[j-len[i]]) f[j]=1;}}}if (f[sum>>1]) g[now]=1;
}
void dfs (int k,int now1,int sum1,int now2,int sum2)  
{  if (k==n)  {  if (g[now1]&&g[now2])ans=max(ans,sum1*sum2/4);  return;  }  dfs(k+1,now1,sum1,now2,sum2);  dfs(k+1,now1+(1<<k),sum1+len[k],now2,sum2);  dfs(k+1,now1,sum1,now2+(1<<k),sum2+len[k]);  
}  
int main()
{n=read();for (int i=0;i<n;i++){len[i]=read();}int N=(1<<n)-1;for (int i=1;i<=N;i++){int sum=0;for (int j=0;j<n;j++){if (i&1<<j) sum+=len[j];}dp(sum,i);}dfs(0,0,0,0,0);if (ans) cout<<ans;else puts("No Solution");return 0;
}