题解分享
题解分享简介
纸币问题 - 题解
```
#include<bits/stdc++.h>
using namespace std;
int a[1010];
int f[10010];
int main(){
int n, cost;
cin>>n>>cost;
for(int i = 1; i <= n; i++){
cin>>a[i];
f[a[i]] = 1;
}
for(int i = 1; i <= cost; i++){
if(f[i]) continue;
int mi = cost;
for(int j = 1; j < n; j++){
if(a[j] > i) continue;
mi = min(f[i - a[j]] + 1 , mi);
}
f[i] = mi;
}
cout<<f[cost];
}
```
查看全文
0
0
0
5
纸币问题 - 题解
```cpp
// https://dashoj.com/p/114
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
vector<int> dp(m + 1, 1e5);
dp[0] = 0;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (a[j] <= i) dp[i] = min(dp[i], dp[i - a[j]] + 1);
cout << dp[m] << endl;
return 0;
}
```
查看全文
0
0
0
2
纸币问题 - 题解
时间复杂度$O(nm)$
空间复杂度$O(m)$
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1010 , M = 1e4 + 10 ;
int f[M] ;
// f[i , j] 表示前 i 种纸币凑出金额为 j 的最少数量
int n , m , a[N] ;
int main(int argc, char const *argv[])
{
cin.tie(nullptr)->ios::sync_with_stdio(false) ;
cin >> n >> m ;
for(int i = 1 ; i <= n ; ++ i) cin >> a[i] ;
memset(f , 0x3f , sizeof f) ;
f[0] = 0 ;
for(int i = 1 ; i <= n ; ++ i)
for(int j = a[i] ; j <= m ; ++ j)
f[j] = min(f[j] , f[j - a[i]] + 1) ;
cout << f[m] << '\n' ;
return 0;
}
```
查看全文
0
0
0
3
纸币问题 - 题解
```
#include<bits/stdc++.h>
using namespace std;
int dp[100001],n,a[101010],cost,w;
int main(){
cin>>n>>w;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1;i <= w;i++){
cost = 0x3f3f3f3f;
for(int j = 1; j <= n; j++){
//特判一下，防止RE
if(i - a[j] >= 0) cost = min(cost, dp[i - a[j]]);
//求之前用的纸币数最小值
}
dp[i] = cost + 1;//加一是这次会多用1张纸币
}
cout << dp[w];
return 0;
}
```
查看全文
0
0
0
1
纸币问题 - 题解
麻烦看看有什么可以优化👀️
```
#include <bits/stdc++.h>
using namespace std;
int main()
{
//输入n张纸币，凑成m元，n赋给cir
int n, m, cir;
cin >> n >> m;
cir = n;
//初始化money数组来接收面额
int money[n] = {0};
while(cir)
{
cin >> money[n-cir];
cir--;
}
//简单排个序
sort(money, money+n);
//从最高面额往下凑
int i = 1, num[n] = {0}, l = n, com;
//大循环是怕3*5这样的例子出现
//不然从最高往下凑会有11的影响
for(;l;l--)
{
com = m;
i = 1;
for(int j = 0; j < l; j++)
{
while(com/money[l-i])
{
num[n-l]++;
com -= money[l-i];
}
i++;
}
}
//找最小值
int* max1 = min_element(num, num+n);
cout << *max1;
}
```
查看全文
0
0
0
1
