问题分析问题描述
逗志芃在干了很多事情后终于闲下来了,然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍,然后选出其中一些粘成一根长的,然后再选一些粘成另一个长的,他想知道在两根一样长的情况下长度最长是多少。
输入格式
第一行一个数n,表示n个棍子。第二行n个数,每个数表示一根棍子的长度。
输出格式
一个数,最大的长度。
样例输入
4
1 2 3 1
样例输出
3
数据规模和约定
n<=15
本题参考了这位博主的解法,讲得很好,点这里看。
这里使用了“0-1背包”的解法,关于“0-1背包”的内容可以看这里。
另外,关于代码中使用到的accumulate求和可以看这里,max_element最大值可以看这里,vector的用法看这里。
代码#includeusing namespace std; int getMaxLength(vector lens) { int n = lens.size(); if(n < 2) return 0; int sum = accumulate(lens.begin(), lens.end(), 0); int maxLen = *max_element(lens.begin(), lens.end()); int target = sum / 2; if(maxLen > target) return 0; vector > dp(n, vector (target+1, 0)); for(int i=0; i > n; vector lens(n); for(int i=0; i > lens[i]; // 目的是在后面删除元素时不用恢复删掉的元素 sort(lens.begin(), lens.end()); int sum = accumulate(lens.begin(), lens.end(), 0); int i = 0; int ans = 0; // 此时可能ans=0,即dp[n-1][weight]!=sum/2 if(sum % 2 == 0) ans = getMaxLength(lens); while(i < lens.size()) { sum = accumulate(lens.begin(), lens.end(), 0) - lens[i]; if(sum % 2 == 0) { lens.erase(lens.begin() + i); ans = max(getMaxLength(lens), ans); i = 0; // 目的是从头开始,有可能在删掉现在的元素后,前面有元素又符合条件了 continue; } i++; } cout << ans << endl; return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)