关注
参考大神的,改了改 贪心或者说是dfs,只要不超时,应该全AC
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int res = 0x7fffffff;
void dfs(vector<int> v, int money, int k, int n)
{
if (money == 0)
{
res = res>k?k:res;
return;
}
if (money < 0 || n < 0 || k > res)
return;
for (int i = money / v[n]; i >= 0; i--)
dfs(v, money - i * v[n], k + i, n - 1);
}
int main()
{
int n;
vector<int> v;
int money;
while (cin >> n)
{
v.push_back(n);
}
money = v[v.size() - 1];
v.pop_back();
sort(v.begin(), v.end());
int days = 0;
dfs(v, money, 0, v.size()-1);
if (res == 0x7fffffff)
res = -1;
cout << res;
//system("pause");
return 0;
}
查看原帖
点赞 评论
牛客热帖
正在热议
# 牛客帮帮团来啦!有问必答 #
1126565次浏览 16884人参与
# 简历无回复,你会继续海投还是优化再投? #
24571次浏览 354人参与
# 不去互联网可以去金融科技 #
10680次浏览 135人参与
# 和牛牛一起刷题打卡 #
17055次浏览 1519人参与
# 通信硬件薪资爆料 #
262570次浏览 2455人参与
# 通信和硬件还有转码的必要吗 #
10444次浏览 98人参与
# OPPO开奖 #
12159次浏览 191人参与
# 互联网公司评价 #
96508次浏览 1252人参与
# 提前批和秋招有什么区别 #
30206次浏览 726人参与
# 你见过最离谱的招聘要求是什么? #
21169次浏览 184人参与
# 参加过提前批的机械人,你们还参加秋招么 #
14405次浏览 349人参与
# 秋招提前批启动你开冲了吗 #
24758次浏览 712人参与
# 面试被问第一学历差时该怎么回答 #
19139次浏览 211人参与
# 如何看待offer收割机的行为 #
249303次浏览 3487人参与
# 快手工作体验 #
70924次浏览 1351人参与
# 你收到了团子的OC了吗 #
535822次浏览 6361人参与
# 现在还是0offer,延毕还是备考 #
412541次浏览 4880人参与
# 提前批的机械人,你们都有面试了吗 #
11366次浏览 158人参与
# 应届生初入职场,求建议 #
35708次浏览 815人参与
# 实习生应该准时下班吗 #
95776次浏览 718人参与
# 晒一晒我的offer #
3805116次浏览 58363人参与
# 工作两年想退休了 #
20370次浏览 262人参与