硬币问题

女爷i 2024-04-17 17:52 61阅读 0赞

#include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 2e5+10;
    const int modd = 1e9+7;
    typedef long long ll;
    
    int n,s;
    int v[maxn],dpm[maxn],dpx[maxn];
    int mini = 999,maxi = -1;
    
    void solve_min(){
        for(int i = 1;i <= s;i++){
            mini = 999;
            for(int j = 1;j <= n;j++){
                if(i-v[j] >= 0) {mini = min(mini,dpm[i-v[j]]+1);}
            }
            dpm[i] = mini;
        }
        for(int i = 1;i <= s;i++){
            cout<<dpm[i]<<" ";
        }
        cout<<endl;
    }
    void solve_max(){
        for(int i = 1;i <= s;i++){
            maxi = -1;
            for(int j = 1;j <= n;j++){
                if(i-v[j] >= 0) {maxi = max(maxi,dpx[i-v[j]]+1);}
            }
            dpx[i] = maxi;
        }
        for(int i = 1;i <= s;i++){
            cout<<dpx[i]<<" ";
        }
        cout<<endl;
    }
    int main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cin>>n>>s;
        for(int i = 1;i <= n;i++){
            cin>>v[i];
        }
        memset(dpm,0,sizeof(dpm));
        memset(dpx,0,sizeof(dpx));
        solve_min();
        solve_max();
        return 0;
    }
    
    /*
    3 10
    2
    3
    4
    
    10 3
    */

发表评论取消回复

表情：

评论列表（有 0 条评论，61人围观）

还没有评论，来说两句吧...

相关阅读

相关硬币问题

include <bits/stdc++.h> using namespace std; const int maxn = 2e5+10;...

女爷i/ 2024年04月17日 17:52/ 0 赞/ 62 阅读

相关凑硬币问题

/ 给出k中面值的硬币，每种硬币的数量无限，再给一个总金额amount，问最少需要几枚硬币凑出这个金额，如果凑不出，返回-1 dp[i]定义：当目标金额为i时，至少

迷南。/ 2022年10月27日 13:54/ 0 赞/ 182 阅读

相关最少硬币问题

最少硬币问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Descri

- 日理万妓/ 2022年05月27日 10:11/ 0 赞/ 210 阅读

相关最少硬币问题（多重背包）

Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description 设

傷城~/ 2022年05月27日 06:15/ 0 赞/ 190 阅读

相关【贪心策略】硬币问题

问题描述：有vi=1元、5元、10元、50元、100元、500元的硬币c1、c2、c3、c4、c5枚。若用这些硬币来凑出A元，最少需要多少枚硬币？贪心策略：初始化n

绝地灬酷狼/ 2022年04月02日 04:18/ 0 赞/ 269 阅读

相关最少硬币问题

最少硬币问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 设有n种不同面值的硬币，

野性酷女/ 2022年02月17日 12:14/ 0 赞/ 211 阅读

相关最少硬币问题

最少硬币问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 设有n种不同面值的硬币，

我就是我/ 2022年02月16日 01:57/ 0 赞/ 242 阅读

相关 1725 最少硬币问题

最少硬币问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 设有n种不同面值的硬币，

傷城~/ 2022年02月15日 06:24/ 0 赞/ 237 阅读

相关动态规划-硬币问题分析

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 什么是动态规划上次对动态规划已经有了个大概的分析

我就是我/ 2022年01月14日 14:47/ 0 赞/ 214 阅读

相关动态规划凑硬币问题

凑硬币问题假设有 1 元，3 元，5 元的硬币若干（无限），现在需要凑出 11 元，问如何组合才能使硬币的数量最少？用数组d来存储当前每个面值可以对应的合成的最小

Dear 丶/ 2021年10月01日 11:34/ 0 赞/ 388 阅读