<>蓝桥杯 试题 算法训练 无聊的逗

问题描述

逗志芃在干了很多事情后终于闲下来了,然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍,然后选出其中一些粘成一根长的,然后再选一些粘成另一个长的,他想知道在两根一样长的情况下长度最长是多少。

样例输入

4
1 2 3 1

样例输出

3

数据规模和约定

n<=15

​ 解题思路:


状态压缩,将所有的状态选中时的值存入数组中,使用公式递推得到所有状态下的长度,最后遍历所有的状态,注意第一层循环只要遍历前一半状态,第二层循环就从第一层状态求补开始遍历,遍历其状态下的所有子状态,最后获取答案并打印
import java.util.Scanner; public class Main { public static void main(String[]
args) { Scanner cin=new Scanner(System.in); int ans=Integer.MIN_VALUE; int n =
cin.nextInt(); int []array=new int[1<<n]; int []nums=new int[n]; for(int i=0;i<n
;++i){ nums[i]=cin.nextInt(); array[1<<i]=nums[i]; } for(int i=0;i<1<<n;++i){
for(int j=0;j<n;++j){ if((i&(1<<j))==0)continue; array[i]=array[i-(1<<j)]+nums[j
]; break; } } for(int i=1;i<(1<<n);++i){ int j=(1<<n)-i-1; for(int k=j;k>0;k=(k-
1)&j){ if(array[k]==array[i]) ans=Math.max(array[k],ans); } } System.out.print(
ans); } }

技术
©2019-2020 Toolsou All rights reserved,
在算法研究过程中如何进行算法创新七大排序算法(java代码)MYSQL中的索引与事务———javaweb(8)(面试必考)2022蓝桥杯JavaB组省赛试题网络安全-wifi攻防网络层协议——ICMP协议MySQL查询表中指定条件下的最新记录JavaSE笔记(一)Java基础语法mysql 查询条件之外的数据_mysql 查询符合条件的数据qt使用数据库sqlite