제출 #1148073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148073		abel	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	1104 ms	191824 KiB

joi2019_ho_t4

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class ResourceAllocator {

    public long calculateOptimalAllocation(List<int[]> resourcePositions, int maxResourceSlots) {
        Map<String, Long> memo = new HashMap<>();
        boolean[] used = new boolean[resourcePositions.size()];
        return dfs(resourcePositions, used, 1, maxResourceSlots, memo);
    }

    private long dfs(List<int[]> resourcePositions, boolean[] used, int placedResources, int maxResourceSlots,
            Map<String, Long> memo) {
        if (placedResources > resourcePositions.size()) {
            return 0;
        }

        String key = generateKey(used, placedResources);
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        long minCost = Long.MAX_VALUE;

        for (int i = 0; i < resourcePositions.size(); i++) {
            if (!used[i]) {
                used[i] = true;
                int[] resource = resourcePositions.get(i);

                int targetRow = (placedResources <= maxResourceSlots) ? 1 : 2;
                int targetCol = (placedResources <= maxResourceSlots) ? placedResources
                        : placedResources - maxResourceSlots;

                long moveCost = Math.abs(resource[0] - targetCol) + Math.abs(resource[1] - targetRow);

                long totalCost = moveCost + dfs(resourcePositions, used, placedResources + 1, maxResourceSlots, memo);

                minCost = Math.min(minCost, totalCost);

                used[i] = false;
            }
        }

        memo.put(key, minCost);
        return minCost;
    }

    private String generateKey(boolean[] used, int placedResources) {
        StringBuilder key = new StringBuilder();
        for (boolean b : used) {
            key.append(b ? "1" : "0");
        }
        key.append(placedResources);
        return key.toString();
    }
}

public class joi2019_ho_t4 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int maxResourceSlots = Integer.parseInt(reader.readLine().trim());
        int totalResources = 2 * maxResourceSlots;

        List<int[]> resourcePositions = new ArrayList<>();
        for (int i = 0; i < totalResources; i++) {
            String[] input = reader.readLine().trim().split(" ");
            resourcePositions.add(new int[] { Integer.parseInt(input[0]), Integer.parseInt(input[1]) });
        }

        ResourceAllocator allocator = new ResourceAllocator();
        long minCost = allocator.calculateOptimalAllocation(resourcePositions, maxResourceSlots);
        System.out.println(minCost);
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63