DFS-HDU 1258-Sum It Up

Love The Way You Lie 2022-05-15 01:19 348阅读 0赞

*  # DFS-HDU 1258-Sum It Up #

--------------------

*  ## 题目链接：[Sum It Up][] ##
 *  ## 思路： ##

### 题目大意： ###

给一个长度n的非递增序列，求和为t的子序列，子序列必须也是非递增序列，而且不能重复

### 题解： ###

用DFS模拟，因为不能重复，把所得数组转成字符串运算式，然后查重

数组转字符串和查重 java还是ok的

**DFS模拟时有一个小细节，当前元素深搜后从已经得到的部分子序列中删除，因为该元素的所有可能结果在深搜时已经查完，所以除去后进入一个新的元素**

*  ### 代码： ###

import java.util.Arrays;
    import java.util.Scanner;
    public class Main {
    	static int[] Res=new int[100];  
    	static int[] Num=new int[100];
    	static String[]	Res_List=new String[100]; //储存结果
    	static boolean Flag;
    	static int Cnt;
    	static int Res_Num;
    	static int n,t;
    	public static void DFS(int Sum,int Index) {
    		if(Sum>t) {
    			return;
    		}
    		if(Sum==t) {
    			Flag=true;
    			String Str="";
    			for(int i=0;i<Cnt;i++) {
    				if(i==0) {
    					Str=Str+Res[i];
    				}else {
    					Str=Str+"+"+Res[i];
    				}
    			}
    			int i=0;
                //查重
    			for(i=0;i<Res_Num;i++) {
    				if(Str.equals(Res_List[i])) {
    					break;
    				}
    			}
    			if(i==Res_Num)
    				Res_List[Res_Num++]=Str;
    			return;
    		}
    		for(int i=Index;i<n;i++) {
    			Res[Cnt++]=Num[i];
    			DFS(Sum+Num[i],i+1);
    			Res[Cnt--]=0;    //已经搜索完的元素出局
    		}
    		return;
    	}
    	public static void main(String[] agrs){
    		Scanner in=new Scanner(System.in);
            
    		while(in.hasNext()) {
    			t=in.nextInt();
    			n=in.nextInt();
    			if(n==0&&t==0)
    				break;
    			for(int i=0;i<n;i++) {
    				Num[i]=in.nextInt();
    			}
    			Flag=false;
    			Cnt=Res_Num=0;
    			System.out.println("Sums of "+t+":");
    			DFS(0,0);
    			if(Flag==false) {
    				System.out.println("NONE");
    			}else {
    				for(int i=0;i<Res_Num;i++) {
    					System.out.println(Res_List[i]);
    				}
    			}
    		}
    	}
    }

[Sum It Up]: http://acm.hdu.edu.cn/showproblem.php?pid=1258