import java.util.Scanner; public class Package01_CostMBuyN {     public static void main(String[] args){         Scanner in = new Scanner(System.in);         int n = in.nextInt();         int[] ps = new int[n];         for(int i = 0; i < n; i++){             ps[i] = in.nextInt();         }         int m = in.nextInt();         int res = solution(ps, m ,n);         System.out.println(res);     }     public static int solution(int[] ps, int m, int n){         int res = -1;         int[][] dp = new int[n+1][m+1];         for(int j = 0; j < m+1; j ++){             dp[0][j] = -1;         }         for(int i = 0; i < n+1; i++){             dp[i][0] = 0;         }         for(int l = 1; l <= n; l++){             for(int r = 1; r <= m; r++){                 int min = Integer.MAX_VALUE;                 dp[l][r] = -1;                 for(int c = 0; c <= r ; c ++){                     int num = 0;                     if((r - c)%ps[l-1] != 0){                         continue;                     }                     int cur = (r - c)/ps[l-1];                     if(dp[l-1][c] == -1){                         continue;                     }else{                         num = dp[l - 1][c] + cur;                     }                     if(num < min ){                         min = num;                         dp[l][r] = min;                     }                 }             }         }         return dp[n][m];     } }
点赞 1
牛客网
牛客企业服务