Untitled
unknown
plain_text
a month ago
2.1 kB
3
Indexable
Never
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