package poj.ProblemSet;

import java.util.Scanner;

public class poj1010 {
    
    public static final int MAXN = 100;
    public static int[] stamp_time = new int[MAXN];
    public static int[] stamp = new int[MAXN];
    public static int[] customer = new int[MAXN];
    public static int[] ans = new int[MAXN];
    public static int stamp_n, customer_n, flag;
    public static int ans_type, ans_total_time, ans_max_stamp;
    public static int now_type, now_total_time, now_max_stamp;

    public static void query() {
        now_type = now_total_time = now_max_stamp = 0;
        for (int i = 1; i <= stamp_n; i++) {
            if (stamp_time[i] > 0) {
                now_type++;
                now_total_time += stamp_time[i];
                if (stamp[i] > now_max_stamp) 
                    now_max_stamp = stamp[i];
            }
        }
    }

    public static void update(int type) {
        ans_type = type;
        ans_total_time = ans_max_stamp = 0;
        for (int i = 1; i <= stamp_n; i++) {
            ans[i] = stamp_time[i];
            if (ans[i] > 0) {
                ans_total_time += ans[i];
                if (stamp[i] > ans_max_stamp) 
                    ans_max_stamp = stamp[i];
            }
        }
    }

    public static void dfs(int cost, int type, int a, int num) {
        if (num > 4 || cost < 0) return;
        if (cost == 0) {
            if (type > ans_type) { flag = 0;update(type); } 
            else if (type == ans_type) {
                query();
                if (now_total_time < ans_total_time) { flag = 0;update(type); } 
                else if (now_total_time == ans_total_time) {
                    if (now_max_stamp > ans_max_stamp) { flag = 0;update(type); } 
                    else if (now_max_stamp == ans_max_stamp) flag = 1;
                }
            }

        }
        for (int i = a; i <= stamp_n; i++) {
            if (i == a) {
                if (type == 0) { stamp_time[a]++;dfs(cost - stamp[a], 1, a, num + 1);stamp_time[a]--; } 
                else { stamp_time[a]++;dfs(cost - stamp[a], type, a, num + 1);stamp_time[a]--; }
            } 
            else { stamp_time[i]++;dfs(cost - stamp[i], type + 1, i, num + 1);stamp_time[i]--; }
        }
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            stamp_n = customer_n = 0;
            for (int i = 0; i < MAXN; i++) stamp_time[i] = stamp[i] = customer[i] = 0;
            do stamp[++stamp_n] = cin.nextInt(); while (stamp[stamp_n] != 0);
            do customer[++customer_n] = cin.nextInt(); while (customer[customer_n] != 0);
            stamp_n--;
            customer_n--;
            for (int i = 1; i <= stamp_n; i++)
                for (int j = i + 1; j <= stamp_n; j++)
                    if (stamp[i] > stamp[j]) {
                        int temp = stamp[i];
                        stamp[i] = stamp[j];
                        stamp[j] = temp;
                    }
            for (int i = 1; i <= customer_n; i++) {
                ans_type = ans_total_time = ans_max_stamp = flag = 0;
                for (int j = 0; j < MAXN; j++) ans[j] = 0;
                dfs(customer[i], 0, 1, 0);
                if (flag == 1) System.out.println(customer[i] + " (" + ans_type + "): tie");
                else if (ans_type > 0) {
                    System.out.print(customer[i] + " (" + ans_type + "):");
                    for (int j = 1; j <= stamp_n; j++) if (ans[j] > 0) while (ans[j]-- > 0) System.out.print(" " + stamp[j]);
                    System.out.println();
                } 
                else System.out.println(customer[i] + " ---- none");
            }
        }
    }
}

• Re:Java 实现，忙了一下午，AC了还是很开心的，贴代码（c++风格） (4019) 3187180646 2024-03-01 14:54:16