硬币问题

女爷i 2024-04-17 17:52 160阅读 0赞
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxn = 2e5+10;
  4. const int modd = 1e9+7;
  5. typedef long long ll;
  6. int n,s;
  7. int v[maxn],dpm[maxn],dpx[maxn];
  8. int mini = 999,maxi = -1;
  9. void solve_min(){
  10. for(int i = 1;i <= s;i++){
  11. mini = 999;
  12. for(int j = 1;j <= n;j++){
  13. if(i-v[j] >= 0) {mini = min(mini,dpm[i-v[j]]+1);}
  14. }
  15. dpm[i] = mini;
  16. }
  17. for(int i = 1;i <= s;i++){
  18. cout<<dpm[i]<<" ";
  19. }
  20. cout<<endl;
  21. }
  22. void solve_max(){
  23. for(int i = 1;i <= s;i++){
  24. maxi = -1;
  25. for(int j = 1;j <= n;j++){
  26. if(i-v[j] >= 0) {maxi = max(maxi,dpx[i-v[j]]+1);}
  27. }
  28. dpx[i] = maxi;
  29. }
  30. for(int i = 1;i <= s;i++){
  31. cout<<dpx[i]<<" ";
  32. }
  33. cout<<endl;
  34. }
  35. int main()
  36. {
  37. ios::sync_with_stdio(0);
  38. cin.tie(0);
  39. cin>>n>>s;
  40. for(int i = 1;i <= n;i++){
  41. cin>>v[i];
  42. }
  43. memset(dpm,0,sizeof(dpm));
  44. memset(dpx,0,sizeof(dpx));
  45. solve_min();
  46. solve_max();
  47. return 0;
  48. }
  49. /*
  50. 3 10
  51. 2
  52. 3
  53. 4
  54. 10 3
  55. */

发表评论

表情:
评论列表 (有 0 条评论,160人围观)

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

相关阅读

    相关 硬币问题

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

    相关 动态规划 凑硬币问题

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