关注
package qunar;
import java.util.Scanner;
public class Main2 {
static int rel =9999;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
String s;
while(in.hasNext()){
s = in.nextLine();
rel = 9999;
gs(s);
if(rel != 9999){
System.out.println(rel);
}else{
System.out.println("-1");
}
}
}
public static void gs(String s){
String[] ar = s.split(" ");
int n = ar.length;
int[] arr = new int[n];
for(int i=0;i<n;i++){
arr[i] = Integer.valueOf(ar[i]);
}
dp(arr,n-2,arr[n-1],0);
}
public static void dp(int[] arr,int now,int money,int day){
if(money < 0){
return;
}
if(money == 0){
if(day < rel){
rel = day;
return ;
}
}
if(money%arr[now] == 0){
if(money/arr[now] < rel){
rel = money/arr[now]+day;
return;
}
}else{
for(int i=now;i>=0;i--){
if(money>=arr[i]){
dp(arr,i,money-arr[i],day+1);
}
}
}
}
}
有一些多余的地方
查看原帖
点赞 2
相关推荐
查看7道真题和解析
点赞 评论 收藏
转发
牛客热帖
正在热议
# 和牛牛一起刷题打卡 #
9298次浏览 810人参与
# 机械制造薪资爆料 #
347761次浏览 4098人参与
# 牛客帮帮团来啦!有问必答 #
1053087次浏览 15961人参与
# 通信硬件薪资爆料 #
250066次浏览 2357人参与
# 你收到了团子的OC了吗 #
524713次浏览 6233人参与
# 毕业租房也有小确幸 #
38124次浏览 3133人参与
# 你怎么评价今年的春招? #
9133次浏览 158人参与
# 晒一晒我的offer #
3722336次浏览 57499人参与
# 提前批和秋招有什么区别 #
28784次浏览 695人参与
# 面试中,你被问过哪些奇葩问题? #
19200次浏览 149人参与
# 秋招开了,你想投哪些公司呢 #
132257次浏览 3421人参与
# 来选选带哪个offer回家过年 #
191472次浏览 1836人参与
# 实习生应该准时下班吗 #
88032次浏览 648人参与
# 你的秋招进行到哪一步了 #
392408次浏览 6638人参与
# 春招你拿到offer了吗 #
397500次浏览 5743人参与
# 腾讯工作体验 #
151044次浏览 1475人参与
# 我想象的工作vs实际工作 #
104051次浏览 1679人参与
# 百度工作体验 #
28502次浏览 286人参与
# 如何写一份好简历 #
308845次浏览 4407人参与
# 担心入职之后被发现很菜怎么办 #
37102次浏览 311人参与