Untitled

mail@pastecode.io avatar
unknown
plain_text
5 months ago
2.1 kB
3
Indexable
import java.util.*;
import java.lang.Math;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Solution {

    public static int minimumCost(int N, List<Integer> A, List<List<Integer>> Cost) {
        // dp[i][j] will store the minimum cost to construct the permutation
        // with the first i elements, when the i-th element is j.
        int[][] dp = new int[N+1][N+1];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);

        // minCost keeps track of the minimum cost encountered so far for each position
        dp[0][0] = 0; // Base case: no elements, no cost

        for (int i = 1; i <= N; i++) {
            int currentA = A.get(i-1);
            for (int j = 1; j <= N; j++) {
                if (j > currentA) continue;
                for (int k = 0; k <= N; k++) {
                    if (dp[i-1][k] != Integer.MAX_VALUE) {
                        dp[i][j] = Math.min(dp[i][j], dp[i-1][k] + Cost.get(i-1).get(j-1));
                    }
                }
            }
        }

        // The result will be the minimum value at dp[N][*] where * ranges from 1 to N
        int result = Integer.MAX_VALUE;
        for (int j = 1; j <= N; j++) {
            result = Math.min(result, dp[N][j]);
        }
        
        return result + 3;
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int N = Integer.parseInt(scan.nextLine().trim());

        List<Integer> A = new ArrayList<>(N);
        for (int j = 0; j < N; j++) {
            A.add(Integer.parseInt(scan.nextLine().trim()));
        }

        List<List<Integer>> Cost = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            Cost.add(
                    Arrays.asList(scan.nextLine().trim().split(" "))
                            .stream().map(s -> Integer.parseInt(s))
                            .collect(toList())
            );
        }
        int result = minimumCost(N, A, Cost);
        System.out.println(result);
    }
}
Leave a Comment