题目
Description
钟逆时针而绕, 恶物狰狞的倾巢, 我谦卑安静地于城堡下的晚祷, 压抑远古流窜的蛮荒暗号, 而管风琴键高傲的说, 那只是在徒劳. 我的乐器在环绕, 时代无法淘汰我霸气的皇朝. 你无法预言, 因为我越险, 翅越艳; 没有句点, 跨时代蔓延, 翼朝天. 月下浮雕, 魔鬼的浅笑, 狼迎风嚎, 蝠翔似黑潮, 用孤独去调尊严的色调. 我跨越过世代, 如兽般的姿态, 琴声唤起沉睡的血脉. 不需要被崇拜, 如兽般的悲哀, 只为永恒的乐曲存在, 醒过来. 去年万众瞩目的《跨时代》专辑发行之后, 周杰伦又开始了他的世界巡回演唱会《超时代》. 有人说过: 如果你喜欢一个人, 那你一定要去看一场他的演唱会; 电视机前的 1m 距离和在演唱会现场哪怕 100m 的距离, 两种感觉都是截然不同的.
所以小 G 作为铁杆歌迷, 也计划带着小 Y 去看周杰伦的演唱会. 演唱会当然要圈出一个空地, 然后才能布置道具. 演唱会的第一站, 公司临时跟当地的消防局借了 n 个栏杆, 打算用这 n 个栏杆围出一个矩形. 而麻烦的是, 这些栏杆有长有短, 这就给围场地带来了一些难度. 所以公司聘请你来写一个程序, 计算用这 n 个栏杆做多围出面积多大的矩形.
- (注: 必须要刚好围成一个矩形, 即不能出现多余的边长, 且不能切断栏杆, 但所给栏杆不一定要全部用上)
- Input
第一行一个正整数 n, 表示栏杆的数量.
第二行 n 个正整数, 表示每根栏杆的长度 li.
Output
仅一行一个正整数, 表示用给出的栏杆围成最大矩形的面积, 如果不能围成矩形, 输出 "No Solution"(不包含引号).
- Sample Input
- 4 1 1 1 1
- Sample Output
- 1
- Data Constraint
- Hint
对于 30% 的数据, 1<=n<=10. 对于 100% 的数据, 1<=n<=16,1<=li<=15.
分析
数据这么小, 应该是个状压
然后 dfs
我们只用先处理出集合是否能构成长宽
代码
- #include<iostream>
- #include<cstring>
- using namespace std;
- int f[2000],g[1<<17],t[20],n;
- void dp(int sum,int x)
- {
- if (sum&1) return;
- memset(f,0,sizeof(f)),f[0]=1;
- for (int i=0;i<n;i++) if (x&1<<i) for (int j=sum;j>=t[i];j--) if (f[j-t[i]]) f[j]=1;
- if (f[sum>>1]) g[x]=1;
- }
- int ans;
- void dfs(int k,int x1,int sum1,int x2,int sum2)
- {
- if (k==n)
- {
- if (g[x1]&&g[x2]) ans=max(ans,sum1*sum2/4);
- return;
- }
- dfs(k+1,x1,sum1,x2,sum2),dfs(k+1,x1+(1<<k),sum1+t[k],x2,sum2),dfs(k+1,x1,sum1,x2+(1<<k),sum2+t[k]);
- }
- int main ()
- {
- cin>>n;
- for (int i=0;i<n;i++)
- cin>>t[i];
- int sum=0;
- for (int i=1;i<=(1<<n)-1;i++)
- {
- sum=0;
- for (int j=0;j<n;j++) if (i&1<<j) sum+=t[j];
- dp(sum,i);
- }
- dfs(0,0,0,0,0);
- if (ans)
- cout<<ans;
- else
- cout<<"No Solution";
- }
来源: http://www.bubuko.com/infodetail-3116651.html