关注
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
相关推荐
查看4道真题和解析 投递用友等公司7个岗位 >
点赞 评论 收藏
转发
牛客热帖
正在热议
# 和牛牛一起刷题打卡 #
4969次浏览 454人参与
# 机械制造薪资爆料 #
341688次浏览 4057人参与
# 牛客帮帮团来啦!有问必答 #
990810次浏览 15332人参与
# 通信硬件薪资爆料 #
242760次浏览 2286人参与
# 腾讯工作体验 #
146943次浏览 1410人参与
# 你觉得机械有必要实习吗 #
10347次浏览 143人参与
# 如何写一份好简历 #
301736次浏览 4333人参与
# 秋招开了,你想投哪些公司呢 #
130007次浏览 3392人参与
# 实习必须要去大厂吗? #
18392次浏览 265人参与
# 你的简历改到第几版了 #
323593次浏览 4864人参与
# 机械制造2024笔面经 #
410196次浏览 6055人参与
# 毕业租房也有小确幸 #
32554次浏览 1959人参与
# 2022毕业生求职现身说法 #
20722次浏览 313人参与
# 0offer互助地 #
53440次浏览 558人参与
# 晒一晒我的offer #
3656595次浏览 56979人参与
# 2022届毕业生现状 #
337605次浏览 4598人参与
# 为什么国企只招应届生 #
56298次浏览 411人参与
# 产品人专业大盘点 #
15131次浏览 120人参与
# 浅聊一下我实习的辛苦费 #
93695次浏览 918人参与
# 视觉/交互/设计岗位评价 #
3378次浏览 61人参与