1558 Euro Efficiency

悲剧的，做了一天，本来用DFS回溯，很快写出了解法，但是发现超时啊。。提交了n次。。研究了半天。。

 

最后放弃，改用另外的做法来做。解题的思路也换了。40分钟搞定了。

 

 

import java.util.Scanner;

/*
 * 思路转换，将题意理解为用6个数填充1-100这个数组，
 * 如1 24 34 39 46 50
 * 那么a[1]=1 a[24]=1 ... a[50]=1，这些为第一层
 * 循环，a[25]（24+1 =25） a[23](24-1=23) = 2...
 * 依次类推，将1,2之类记为层数，n即位2数的层数之和，a[25]即为层数为2（n==2）的层数构成
 * 第一次，先记录层数为1的数，即currency
 * 第2次先产生层数为2的数，第3次产生层数为1+2 或2+1的数
 * 第i次产生层数为 i + n-i的数
 * 思路如此。。。继续编码
 */
public class Main {
	
	public static void main(String[] args) {
		int currency[] = {1, 24, 34, 39, 46, 50};
		
		
		Scanner sc = new Scanner(System.in);
		int num = Integer.parseInt(sc.next());
		do{
			getCurrency(sc, currency);
			num --;
			calculate(currency);
		}while(num != 0);
	}
	public static void getCurrency(Scanner sc, int [] currency){
		for(int i = 0; i < 6; i ++){
			currency[i] = sc.nextInt();
		}
	}
	public static void calculate(int currency[]){
		int res[] = new int[101];
		for(int i = 0 ; i < 6 ; i ++){//产生第一层
			res[currency[i]] = 1;
		}
		int count = 6;
		int n = 2;//层次之和
		while(count < 100){//跳出循环的条件为count == 100
			for(int i = 1 ; i < 101; i ++){
				for(int j = 1 ; j < 101 ; j ++){
					for(int k = 1 ; k < n; k ++){//控制层数
						if(res[i] == k && res[j] == n-k){
							if( i + j <= 100 &&res[i + j] == 0){
								res[i+j] = n;
								count ++;
							}
							if(i != j && res[Math.abs(i-j)] == 0){
								res[Math.abs(i-j)] = n;
								count ++;
							}
						}
					}
				}
			}
			n ++;
		}
		double sum = 0;
		int max = 0;
		for(int i = 1 ; i < 101 ; i ++){
			sum += res[i];
			if(max < res[i]){
				max = res[i];
			}
		}
		System.out.printf("%.2f %d\n", sum/100, max);
	}
}

//另附上弄了好久的代码，虽然超时。。但是也搞了好久。。不留作纪念说不过去。。悲剧！

import java.util.Scanner;
/*
 * 悲剧的超时了
 * DFS暴力
 */
public class EuroEfficiency {

	public static int []currency = new int[6];
	public static int result[] = new int[201];//-100 -1 0(->100) 1 100	共201个
	public static int res = 101;
	public static void calculate(int money, int total){
		if(money == 0){
			if(res > total){
				res = total;
			}
			return ;
		}
		if(total >= res){
			return ;
		}
		if(money >0){
			for(int i = 5; i >= 0; i --){
				if(total + 1 >= res ){
					break;
				}
				if(money - currency[i] >= (-1 * currency[5])){
					if(result[money - currency[i] + 100] != 0){
						calculate(0, total + result[money - currency[i] + 100]+1);
					}else{
						calculate(money - currency[i], total + 1 );
					}
				}
			}
		}else{
			for(int i = 0; i <6; i ++){
				if(total + 1 >= res ){
					break;
				}
				if(money + currency[i] <= currency[5]){
					if(result[money + currency[i] + 100] != 0){
						calculate(0, total + result[money + currency[i] + 100]+1);
					}else{
						calculate(money + currency[i], total + 1 );
					}
				}
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		do{
			getCurrency(sc);
			n --;
			double sum = 0;
			int max = 1;
			for(int i = 1; i <= 100; i ++){
				res = 101;
				calculate(i, 0);
				result[i+100] = res;
				sum += res;
				if(res > max){
					max = res;
				}
			}
			for(int i = 100 ; i < 201; i ++){
				System.out.println(result[i]);
			}
			
			System.out.printf("%.2f %d\n",sum/100, max);
		}while(n != 0);
	}
	
	public static void getCurrency(Scanner sc){
		result = new int[201];
		for(int i = 0; i < 6; i ++){
			currency[i] = sc.nextInt();
		}
	}
}