fork download
copy 
  1. //https://c...content-available-to-author-only...s.fi/problemset/task/1634
  2. /*
  3. dp[i] số đồng xu tối thiểu để đạt được tổng giá trị của các đồng xu là i
  4. */
  5. #include<bits/stdc++.h>
  6. using namespace std;
  7. const long long MaxN = 1e6 + 5, INF = 1e18;
  8. long long n,x,dp[MaxN], c[MaxN];
  9. void input()
  10. {
  11.     cin >> n >> x;
  12.     for (long long i=1; i<=n; i++)
  13.     {
  14.         cin >> c[i];
  15.     }
  16. }
  17. void solve1() // xuôi
  18. {
  19.     memset(dp,0x3f,sizeof(dp)); // các trường hợp còn lại bằng -1 do chưa thăm hay chưa tồn tại
  20.     dp[0]=0; //trường hợp base ko có cách chọn nào tổng bằng 0 do các đồng xu đều có giá trị nguyên dương
  21.     for (long long i=0; i<x; i++)
  22.     {
  23.         if(dp[i]>-1) // nếu tồn tại cách chọn với i rồi thì mới so sánh được dp[i]+1 và dp[i+c[j]]
  24.         {
  25.             for (long long j=1; j<=n; j++)
  26.             {
  27.                 if(i+c[j]<=x) // vì kết quả bài toán cần tìm là x nên >x là vô nghĩa vì dp[x] chỉ cần tạo thành từ dp[t] với t<x
  28.                 {
  29.                 dp[i+c[j]]=min(dp[i+c[j]],dp[i]+1);
  30.                 }
  31.             }
  32.         }
  33.     }
  34.     if(dp[x]>=INF)
  35.     {
  36.         cout << -1;
  37.     }
  38.     else
  39.     {
  40.         cout << dp[x];
  41.     }
  42. }
  43. void solve2()
  44. {
  45.     memset(dp,0x3f,sizeof(dp)); // các trường hợp còn lại bằng -1 do chưa thăm hay chưa tồn tại
  46.     dp[0]=0; //trường hợp base ko có cách chọn nào tổng bằng 0 do các đồng xu đều có giá trị nguyên dương
  47.     for (long long i=1; i<=x; i++)
  48.     {
  49.         for (long long j=1; j<=n; j++ )
  50.         {
  51.             if(i-c[j]>=0)// trường hợp âm sẽ bị bug 
  52.             {
  53.                 dp[i]=min(dp[i],dp[i-c[j]]+1);
  54.             }
  55.         }
  56.     }
  57.     if(dp[x]>=INF)
  58.     {
  59.         cout << -1;
  60.     }
  61.     else
  62.     {
  63.         cout << dp[x];
  64.     }
  65. }
  66. int main()
  67. {
  68.     ios_base::sync_with_stdio(0);
  69.     cin.tie(0);
  70.     input();
  71.     solve2();
  72.     return 0;
  73. }
Success #stdin #stdout 0.01s 13496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gkWcoA
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!