5 条题解
-
0
// 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
#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
#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
时间复杂度
空间复杂度
#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
麻烦看看有什么可以优化👀️
#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; }
- 1
信息
- ID
- 114
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 416
- 已通过
- 113
- 上传者