hdu4277搜索

本文主要是介绍hdu4277搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你n个有长度的线段，问如果用上所有的线段来拼1个三角形，最多能拼出多少种不同的？

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NavigableSet;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;import org.omg.CORBA.Object;public class Main {public static void main(String[] args) throws IOException{StreamTokenizer cin = new StreamTokenizer(new BufferedInputStream(System.in)); InputReader in = new InputReader(System.in)  ;PrintWriter out = new PrintWriter(System.out) ;int t = in.nextInt() ;for(int cas = 1 ; cas <= t ; cas++){new Task().solve(in, out)  ;  // out.flush() ;}out.flush() ; }}class   Task{Set st ;int[] val ;  int n ; long sum ;void dfs(int a , int b , int c , int id){if(a > sum/3) return ;if(id == n){if(a <= b && b <= c){if(a + b > c && a + c > b && b + c > a){st.insert( sum * sum * a + sum * b +  c ) ;}}return ;}dfs(a+val[id] , b , c , id+1) ;dfs(a , b+val[id] , c , id+1) ;dfs(a , b , c+val[id], id+1) ;}public void solve(InputReader  in , PrintWriter out) throws IOException{n = in.nextInt() ;st = new Set() ;val = new int[n] ;sum = 0 ;for(int i = 0 ; i < n ; i++){val[i] = in.nextInt() ;sum += val[i] ;}dfs(0 , 0 , 0 , 0) ;out.println(st.size) ;}}class  Set{static  long  MOD = 1000007L ;static  long[] val =  new long[(int)MOD + 10] ;static  int[] head = new int[(int)MOD] ;static  int[] next = new int[(int)MOD + 10] ;int  size  ;public  Set(){Arrays.fill(head, -1) ; size = 0 ;}public  void clear(){Arrays.fill(head, -1) ; size = 0 ; }public  boolean  find(long x){long u = (x % MOD + MOD) % MOD ;for(int i = head[(int)u] ; i != -1 ; i = next[i]){if(val[i] == x) return true ;}return false ;}public  void  insert(long x){if(find(x)) return ;long u = (x % MOD + MOD) % MOD ;val[size] = x ;next[size] = head[(int)u] ;head[(int)u] = size++ ;}}class InputReader{public BufferedReader  reader;public StringTokenizer  tokenizer;public InputReader(InputStream stream){reader = new BufferedReader(new InputStreamReader(stream), 32768) ;tokenizer = null ;}public String next(){while(tokenizer == null || ! tokenizer.hasMoreTokens()){try{tokenizer = new StringTokenizer(reader.readLine());}catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}}

这篇关于hdu4277搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---