问题描述
逗志芃在干了很多事情后终于闲下来了,然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍,然后选出其中一些粘成一根长的,然后再选一些粘成另一个长的,他想知道在两根一样长的情况下长度最长是多少。
输入格式
第一行一个数n,表示n个棍子。第二行n个数,每个数表示一根棍子的长度。
输出格式
一个数,最大的长度。
样例输入
4
1 2 3 1
1 2 3 1
样例输出
3
参考代码:
#include <bits/stdc++.h> using namespace std; // 如果两个子集的元素和相等时,返回nums总和除以 2,否则返回 0 int getPartitionValue(vector<int> nums) { int n = nums.size(); if (n < 2) { return false; } int sum = accumulate(nums.begin(), nums.end(), 0); int maxNum = *max_element(nums.begin(), nums.end()); if (sum & 1) return 0; int target = sum / 2; if (maxNum > target) return 0; // 建立背包 vector<vector<int> > dp(n, vector<int>(target + 1, 0)); // 初始化背包 for (int i = 0; i < n; i++) dp[i][0] = 0; for (int j = nums[0]; j <= sum/2; j++) dp[0][j] = nums[0]; for (int i = 1; i < n; i++) { for (int j = 1; j <= target; j++) { if (j < nums[i]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]); } } } return dp[n - 1][target] == sum/2 ? sum/2 : 0; } int main() { int n; cin>>n; vector<int> nums(n); for (int i = 0; i < n; ++i) cin>>nums[i]; sort(nums.begin(), nums.end()); // 排序 int sum = accumulate(nums.begin(), nums.end(), 0); // 累加 int i = 0; int ans = 0; if (sum % 2 == 0) ans = getPartitionValue(nums); // 如果每次总和是偶数,都去判断是否存在可分成使得两个子集的元素和相等,如果存在返回值,否则返回 0, 每次去最大值 while (i < nums.size()) { sum = accumulate(nums.begin(),nums.end(), 0); if ((sum - nums[i]) % 2 == 0) { nums.erase(nums.begin()+i); // 删除这个元素 ans = max(getPartitionValue(nums), ans); // 每次去最大值 i = 0; // i 置为 0 continue; } i++; } cout<<ans<<endl; return 0; }
相关文章
- 1 信息学奥赛一本通1001:Hello,World答案及题解
- 2 信息学奥赛一本通C++练习题: 求10000以内n的阶乘
- 3 信息学奥赛一本通C++练习题: 大整数的因子
- 4 信息学奥赛一本通C++练习题: 计算2的N次方
- 5 信息学奥赛一本通C++练习题: 大整数减法
- 6 信息学奥赛一本通C++练习题: 大整数加法
- 7 信息学奥赛C++一本通练习题: 回文数。
- 8 2023年5月电子学会C语言等级考试1~8级真题及答案
- 9 单词分析:小蓝正在学习一门神奇的语言,这门语言
- 10 生理周期:给定时间为10,下次出现三个高峰同天的时间是12,则输出2
- 11 Scratch青少年等级考试一级编程题:猫捉老鼠
- 12 2023年5月青少年软件编程C语言三级等级考试
- 13 2023年3月电子学会Scratch等级考试试卷一级编程真题
- 14 回文日期:2020 年春节期间,有一个特殊的日期引起了大家的注意:
- 15 蓝桥杯比赛5道Scratch编程题答案及代码
- 16 2023年3月电子学会Scratch等级考试四级真题
- 17 2023年3月份的蓝桥杯STEMA测评真题
- 18 盈亏问题:假设有一群人买一件物品,如果每个人出a元,
- 19 Python编程等级考试真题彩色螺旋文字
- 20 Python等级考试试卷(五级)及答案
-
扫码下载安卓APP
-
微信扫一扫关注我们
微信扫一扫打开小程序
手Q扫一扫打开小程序
-
返回顶部
友情链接:
6547题库网 |
Scratch从入门到精通|
Copyright © 小码农 |
2020-2022
发表评论