首页 > 专题系列 > Java解POJ > POJ 3677 Chemical Weighing [解题报告] Java
2013
11-13

POJ 3677 Chemical Weighing [解题报告] Java

Chemical Weighing

问题描述 :

Facer is the chemical keeper in a laboratory. Every day he receives M requests of a certain kind of chemical which is vital to a large variety of experiments. The ith request asks for Ri grams of the chemical and Facer has to weigh the chemicals in the exact order as the requests listed or he will mess up all the experiments.

The balance used in the laboratory has N different kinds of poises. The ith kind weighs Wi grams. The amount of poises of each kind is so large that can be considered as infinite. The poises are all in a flat shape. When Facer wants to weigh the chemical, he has to stack the poises on the left side of the balance one by one in such a way that the lighter ones are always above the heavier ones. For example, a 2-gram poise is never allowed to be on the top of a 1-gram poise.

To accelerate his work, Facer tries to use the minimum steps to finish the weighing. For each step he can put one poise on the top of the stack (as long as no poises in the stack is lighter than it) or remove the poise which is currently on the top.

输入:

The first line of the input contains the number of the test cases.
Each test case follows the format below:

  • One line contains an integer N (1 ≤ N ≤ 15), the number of different kinds of poises
  • One line contains N integers, W1, W2WN, ( 1 ≤ Wi ≤ 30)
  • One line contains an integer M (1 ≤ M ≤ 500), the number of requests
  • One line contains M integers, R1, R2, … RM ( 1 ≤ Ri ≤ 30)

输出:

For each test case, output a line containing the minimum number of steps Facer needed to finish all the requests. If any request can not be weighed out, output -1 instead.

样例输入:

2
3
1 2 3
3
4 5 6
2
3 4
3
1 6 8

样例输出:

4
-1

解题代码:

//* @author 
import java.util.*;
import java.io.*;

class Main
{
 static int armor[];
 final static int MAX = 1000000;
 static class Node
 {
	Node l = null, r = null;
	int flag, step, value;
	Node(int k, int v)
	{
         flag = 0;
	 step = MAX;
	 value = v;
	 if(k>=0&&v<=30)
	 {
		l = new Node(k, v+armor[k]);
		r = new Node(k-1, v);
	 }
	}
	

  int update(int f, int v, int s)
  {
	if(value>v||l==null&&r==null)return MAX;
	if(f==flag)step = Math.min(s, step);
	else step = s;
	s = step;
	flag = f+1;
	//System.err.println(value+":"+s);
	if(value==v)return s;
	return step = Math.min(l.update(f, v, s+1)+1, r.update(f, v, s));
  }
  int query(int v)
  {
	if(l==null&&r==null)return MAX;
	if(value==v)return step;
	return Math.min(l.query(v), r.query(v));
  }
 }

 public static void main(String[] args) throws IOException
 {
  Scanner in = new Scanner(System.in);
  for(int T = in.nextInt(); T!=0; --T)
  {
	int n = in.nextInt();
	armor = new int[n];
	for(int i=0; i!=n; ++i)
		armor[i] = in.nextInt();
	Arrays.sort(armor);
	int cnt=0;
	Node root = new Node(n-1, 0);
	root.step = 0;
	int k = 0, m = in.nextInt();
	for(int i=0; i!=m; ++i)
		root.update(cnt++, k=in.nextInt(), MAX);
	k = root.query(k);
	if(k==MAX)System.out.println(-1);
	else System.out.println(k);
    }
  }
}