algorithms software expert

소프트웨어 익스퍼트 1952 (software expert 1952)

소프트웨어 익스퍼트 1952 (software expert 1952)

목차

소프트웨어 익스퍼트 1952

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class SWE1952 {
    static int t, T, n, costs[] = new int[4], sch[] = new int[13], v, min;
    static int dp[][] = new int[13][13];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        t = T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- != 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            v = 0;
            while (st.hasMoreTokens()) {
                costs[v++] = Integer.parseInt(st.nextToken());
            }
            v = 1;
            st = new StringTokenizer(br.readLine(), " ");
            while (st.hasMoreTokens()) {
                sch[v++] = Integer.parseInt(st.nextToken());
            }
            for (int i = 1; i < 13; i++) {
                Arrays.fill(dp[i], 3000001);
            }
            dp[1][1] = (costs[0] * sch[1] < costs[1]) ? costs[0] * sch[1] : costs[1];
            dp[1][3] = costs[2];
            dp[1][12] = costs[3];

            for (int i = 2; i <= 12; i++) {
                for (int j = 1; j < i; j++) {
                    dp[i][i] = Math.min(dp[i][i], dp[j][i - 1] +
                            ((costs[0] * sch[i] < costs[1]) ? costs[0] * sch[i] : costs[1]));
                    if (i + 2 < 13)
                        dp[i][i + 2] = Math.min(dp[i][i + 2], dp[j][i - 1] + costs[2]);
                }
                for (int j = i; j <= 12; j++) {
                    for (int k = 1; k < i; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[k][j]);
                    }
                }

            }

            sb.append("#");sb.append(t - T);sb.append(" ");
            sb.append(dp[12][12]);sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();bw.close();
    }


}

설명