ZOJ 문제 세트 - 1013 Great Equipment Java 구현

이 문 제 는 python 으로 오랫동안 풀 었 는데, 시스템 은 줄곧 시간 을 초과 하 였 다.코드 에 4 층 짜 리 순환 이 있 기 때문에 python 의 2 차원 배열 은 효율 이 높 지 않 은 것 같 습 니 다.어젯밤 에 도 잠 자기 전 까지 만 들 지 못 했 기 때문에 자바 가 될 수 있 는 지 없 는 지 시험 해 보 려 고 합 니 다.아침 에 일어나 자마자 자바 버 전 코드 를 쓰기 시 작 했 는데 몇 번 만 에 AC 가 됐어 요.결론 은 다음 에 다 중 순환 상황 에 부 딪 히 면 python 이 감당 하지 못 하면 자바 를 고려 할 수 있다 는 것 이다.하지만 필자 의 python 이 안 되 기 때 문 일 수도 있 습 니 다.
다음은 AC 의 자바 코드 입 니 다.

import java.io.IOException;

import java.util.Scanner;

 
public class Main {

 
    public static void main(String[] args) throws IOException {

        final int MAX_SIZE = 501;

        //          

        // pre_carry[i][j]      i，    j     

        int[][] pre_carry = new int[MAX_SIZE][MAX_SIZE];

        //                 

        int[][] current_carry = new int[MAX_SIZE][MAX_SIZE];

        //     

        int w1, s1, d1, w2, s2, d2, w3, s3, d3, c1, c2, c3, d4;

        Scanner cin = new Scanner(System.in);

        int no = 1;

        while (true) {

            int n = cin.nextInt();

            if (n == 0) {

                break;

            }

            //       

            w1 = cin.nextInt();

            s1 = cin.nextInt();

            d1 = cin.nextInt();

            w2 = cin.nextInt();

            s2 = cin.nextInt();

            d2 = cin.nextInt();

            w3 = cin.nextInt();

            s3 = cin.nextInt();

            d3 = cin.nextInt();

            c1 = cin.nextInt();

            c2 = cin.nextInt();

            c3 = cin.nextInt();

            d4 = cin.nextInt();

 
            for (int i = 0; i < MAX_SIZE; i++) {

                for (int j = 0; j < MAX_SIZE; j++) {

                    pre_carry[i][j] = -1;

                }

            }

            // pre_carry[0][0] 0          

            pre_carry[0][0] = 0;

            //   n      ，      ，      

            //   pre_carry           

            while (n > 0) {

                int w = cin.nextInt();

                int s = cin.nextInt();

                for (int i = 0; i < MAX_SIZE; i++) {

                    for (int j = 0; j < MAX_SIZE; j++) {

                        current_carry[i][j] = -1;

                    }

                }

                // i    ，j    ，k    

                for (int i = 0; w - i * w1 >= 0 && s - i * s1 >= 0; i++) {

                    for (int j = 0; w - i * w1 - j * w2 >= 0

                            && s - i * s1 - j * s2 >= 0; j++) {

                        int w_remain = w - i * w1 - j * w2;

                        int s_remain = s - i * s1 - j * s2;

                        int k = Math.min(w_remain / w3, s_remain / s3);

                        //            ，          current_carry 

                        for (int ii = 0; ii < MAX_SIZE; ii++) {

                            for (int jj = 0; jj < MAX_SIZE; jj++) {

                                if (pre_carry[ii][jj] == -1) {

                                    break;

                                }

                                current_carry[ii + i][jj + j] = Math.max(

                                        current_carry[ii + i][jj + j], k

                                                + pre_carry[ii][jj]);

                            }

                        }

                    }

                }

                //         

                int[][] temp = pre_carry;

                pre_carry = current_carry;

                current_carry = temp;

                n--;

            }

            //        ，pre_carry          

            //            ，     

            int max_defend = 0;

            for (int i = 0; i < MAX_SIZE; i++) {

                for (int j = 0; j < MAX_SIZE; j++) {

                    if (pre_carry[i][j] >= 0) {

                        int defend = 0;

                        if (d4 > c1 * d1 + c2 * d2 + c3 * d3) {

                            int set_num = Math.min(i / c1,

                                    Math.min(j / c2, pre_carry[i][j] / c3));

                            defend = set_num * d4;

                            defend += (i - set_num * c1) * d1

                                    + (j - set_num * c2) * d2

                                    + (pre_carry[i][j] - set_num * c3) * d3;

                        } else {

                            defend = i * d1 + j * d2 + pre_carry[i][j] * d3;

                        }

                        max_defend = Math.max(max_defend, defend);

                    }

 
                }

            }

            if (no == 1) {

                System.out.print("Case " + no + ": " + max_defend);

            } else {

                System.out.print("

Case " + no + ": " + max_defend);

            }

            no++;

        }

    }

 
 

}