Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1010 STAMPS 总么一直runtime error ,求高手解答

Posted by yfkscugs at 2010-10-18 16:10:22
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	private int kinds = 0;
	private final int size = 1000;
	private int[] values = new int[size];
	private int[] currPath = new int[size];
	private int[] path = new int[size];
	private int level;
	private int numOfKinds = 0;
	private int num = 0;
	private int maxValue = 0;
	private int numOfSame = 0;
	private int remainValue = 0;
	private int remainNum = 0;

	public static void main(String[] args) {
		Main m = new Main();
		m.start();
	}

	public void start() {
		Scanner scanner = new Scanner(System.in);
		String line = null;
		while ((line = scanner.nextLine()) != null) {
			kinds = 0;
			int count = 1;
			StringTokenizer st = new StringTokenizer(line);
			while (st.hasMoreTokens()) {
				int v = Integer.parseInt(st.nextToken());
				if (v == 0)
					break;
				values[count++] = v;
				kinds++;
			}
			st = new StringTokenizer(scanner.nextLine());
			while (st.hasMoreTokens()) {
				int value = Integer.parseInt(st.nextToken());
				if (value == 0)
					break;

				numOfKinds = 0;
				num = 0;
				maxValue = 0;
				numOfSame = 0;
				remainNum = 4;
				remainValue = value;
				level = kinds;

				des(1);

				if (numOfSame == 0) {
					System.out.println(value + " ---- none");
				} else if (numOfSame > 1) {
					System.out.println(value + " (" + numOfSame + "): tie");
				} else {
					System.out.print(value + " (" + numOfKinds + "): ");
					for (int i = 1; i <= path[0]; i++) {
						int tmpCount = path[i];
						while (tmpCount > 0) {
							System.out.print(values[i] + " ");
							tmpCount--;
						}
					}
					System.out.println();
				}
			}
		}
	}

	public int[] check(int[] a) {
		int num = 0;
		int kind = 0;
		int maxValue = 0;
		for (int i = 1; i <= a[0]; i++) {
			if (a[i] != 0) {
				num += a[i];
				kind++;
				if (values[i] > maxValue)
					maxValue = values[i];
			}
		}
		return new int[] { kind, num, maxValue };
	}

	public void update(int[] result) {
		numOfKinds = result[0];
		num = result[1];
		maxValue = result[2];
	}

	public void copy(int[] src, int[] dest) {
		int n = src[0];
		for (int i = 0; i <= n; i++) {
			dest[i] = src[i];
		}
	}

	public void des(int currLevel) {

		if (currLevel > level)
			return;

		if (remainNum <= 0)
			return;

		for (int i = 0; i <= remainNum; i++) {
			currPath[0] = currLevel;

			if (remainValue - i * values[currLevel] < 0)
				break;

			currPath[currLevel] = i;
			remainNum -= i;
			remainValue -= i * values[currLevel];

			if (remainValue == 0) {
				int[] result = check(currPath);
				if (numOfSame == 0) {
					numOfSame = 1;
					update(result);
					copy(currPath, path);
				} else {
					if (result[0] > numOfKinds) {
						numOfSame = 1;
						update(result);
						copy(currPath, path);
					} else if (result[0] == numOfKinds && result[1] < num) {
						numOfSame = 1;
						update(result);
						copy(currPath, path);
					} else if (result[0] == numOfKinds && result[1] == num
							&& result[2] > maxValue) {
						numOfSame = 1;
						update(result);
						copy(currPath, path);
					} else if (result[0] == numOfKinds && result[1] == num
							&& result[2] == maxValue) {
						numOfSame++;
					}
				}
			} else if (remainValue > 0 && currLevel < level) {
				des(currLevel + 1);
			}

			remainNum += i;
			remainValue += i * values[currLevel];
		}
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator