<> Blue Bridge Cup test questions Algorithm training Boring funny
Problem description
After doing a lot of things, Dou Zhipeng finally got free , And then I fell into deep boredom . But he thought of a game to make him more boring . He took out n A wooden stick , Then select some of them and stick them into a long one , Then choose some and stick them into another long one , He wanted to know what was the longest length when two were the same length .
sample input
4
1 2 3 1
sample output
3
Data scale and agreement
n<=15
Problem solving ideas ：
State compression , Store all the values in the selected state into the array , Use formula recursion to get the length in all States , Finally, traverse all States , Note that the first level loop only traverses the first half of the state , The second level loop starts from the state complement of the first level , Traverse all sub states in its state , Finally, get the answer and print it
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); } }
Technology
Daily Recommendation