5 条题解

  • 0
    @ 2025-4-10 3:42:52
    // 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
      @ 2025-3-28 10:29:54
      #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
        @ 2024-8-27 17:42:01
        #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
          @ 2024-5-2 1:05:48

          时间复杂度O(nm)O(nm)

          空间复杂度O(m)O(m)

          #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
            @ 2024-4-9 10:49:36

            麻烦看看有什么可以优化👀️

            #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
            上传者