赞
踩
时间限制:1.0s 内存限制:256.0MB
逗志芃在干了很多事情后终于闲下来了,然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍,然后选出其中一些粘成一根长的,然后再选一些粘成另一个长的,他想知道在两根一样长的情况下长度最长是多少。
第一行一个数n,表示n个棍子。第二行n个数,每个数表示一根棍子的长度。
一个数,最大的长度。
- 4
- 1 2 3 1
3
n<=15
- #include <bits/stdc++.h>
- using namespace std;
- int a[15];
- int b[1 << 15]; //2^15
- //假设有四根木棍,则 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
- // 1代表取,0代表不取,即每根木棍取与不取的所有组合情况,共2^4种组合
- int main() {
- int n;
- cin >> n;
- for (int i = n - 1; i >= 0; i--) { //让木棍在数组中以倒序排列,这样 取0010 = 2^1 即取a[1] = 3
- cin >> a[i];
- }
- //原:1 2 3 1
- //倒序:1 3 2 1
- //求每一个组合的木棍的长度
- for (int i = 0; i < (1 << n); i++) { //0 ~ 2^n的所有数,即所有组合取用木棍的情况(不要用pow(2,n),效率比二进制移位低,会超时)
- for (int j = 0; j < n; j++) { //n根木棍
- if (i & (1 << j)) //i分别按位与 0001 0010 0100 1000,说明这个组合选用了这根木棒
- b[i] += a[j];
- }
- }
- //木棍分别为 1 2 3 1
- //0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 //i:所有组合取用木棍的情况,0不选;1选
- //0000 0001 0030 0031 0200 0201 0230 0231 1000 1001 1030 1031 1200 1201 1230 1231 //实际的木棍选用情况
- // 0 1 3 4 2 3 5 6 1 2 4 5 3 4 6 7 //b[i]:每种组合的长度
- int ans = 0;
- //将这个组合和其它组合进行比较,如果其它组合和这个组合中没有选用相同的木棍,并且这两个组合长度相等,则符合条件,进而与最大长度比较和替换。
- for (int i = 0; i < (1 << n); i++) {
- for (int j = 0; j < (1 << n); j++) {
- if (!(i & j) && b[i] == b[j]) {
- ans = max(ans, b[i]);
- }
- }
- }
- cout << ans;
- return 0;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。