글 읽기 - 반례를 찾고 싶어요.

dnatuna 2년 전 0

반례를 찾고 싶어요.

밑의 글에서 올려주신 두 개의 예제를 다 돌려도 답이 나옵니다. ㅠㅠ

import java.io.*;
import java.util.*;

public class Main {
    static class Pair {
        int cpu;
        int memory;
        int priority;

        public Pair(int memory, int priority) {
            this.cpu = 0;
            this.memory = memory;
            this.priority = priority;
        }

        public Pair(int cpu, int memory, int priority) {
            this.cpu = cpu;
            this.memory = memory;
            this.priority = priority;
        }

        public int getCpu() { return this.cpu; }
        public int getMemory() { return this.memory; }
        public int getPriority() { return this.priority; }
    }

    static Pair[][] memo;
    static int n, m, k;
    static int addCpu=0, addMemory=0;

    public static void dp(int i,int cpu, int memory, int priority) {
        for(int j=1; j<=addCpu; ++j) {
            int tmpCpu = j-cpu;
            if(tmpCpu < 0) continue;
            int nowMemory = memo[i-1][tmpCpu].getMemory() + memory;
            int nowPriority = memo[i-1][tmpCpu].getPriority() + priority;
            if(nowMemory < k) {
                if(nowMemory >= memo[i-1][j].getMemory()) {
                    memo[i][j] = new Pair(nowMemory, nowPriority);
                } else {
                    memo[i][j] = new Pair(memo[i-1][j].getMemory(), memo[i-1][j].getPriority());
                }
            } else {
                if(memo[i-1][j].getMemory() < k) {
                    memo[i][j] = new Pair(nowMemory, nowPriority);
                } else if(nowPriority < memo[i-1][j].getPriority()) {
                    memo[i][j] = new Pair(nowMemory, nowPriority);
                } else {
                    memo[i][j] = new Pair(memo[i-1][j].getMemory(), memo[i-1][j].getPriority());
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); k = Integer.parseInt(st.nextToken());

        Pair[] list = new Pair[n+1];
        for (int i = 1; i <= n; ++i) {
            st = new StringTokenizer(br.readLine());
            int cpu = Integer.parseInt(st.nextToken()), memory = Integer.parseInt(st.nextToken()), priority = Integer.parseInt(st.nextToken());
            addCpu += cpu; addMemory += memory;
            list[i] = new Pair(cpu, memory, priority);
        }

        memo = new Pair[n+1][addCpu+1];
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= addCpu; ++j)
                memo[i][j] = new Pair(0, 0, 0);


        if(addCpu < m && addMemory < k) {
            System.out.println(-1);
        } else {
            for (int i = 1; i <= n; ++i) {
                dp(i, list[i].getCpu(), list[i].getMemory(), list[i].getPriority());
            }
            System.out.println(memo[n][addCpu].getPriority());
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 찾고 싶어요.

dnatuna 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말