fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // có 3 đồng xu, có bao nhiêu cách chọn để tổng giá trị bằng s
  5. // gọi f[i] là số đồng xu lớn nhất để chọn để tổng giá trị bằng i
  6. // f[0] = 0;
  7. // f[i] = max(f[i-a], f[i-b], f[i-c]) + 1
  8.  
  9. // f[n]
  10. // 6 đ: 3 cách
  11. // 5 đ: 2 cách
  12.  
  13. int main(){
  14.     vector<int> f(4005,-1);
  15.     int s, a, b, c;
  16.     cin >> s >> a >> b >> c;
  17.     f[0] = 0;
  18.  
  19.     for(int i = 0; i <= s; i++){
  20.         if(i-a >= 0 && f[i-a] != -1) f[i] = max(f[i], f[i-a] + 1);
  21.         if(i-b >= 0 && f[i-b] != -1) f[i] = max(f[i], f[i-b] + 1);
  22.         if(i-c >= 0 && f[i-c] != -1) f[i] = max(f[i], f[i-c] + 1);
  23.        /*
  24.         if(f[i] != -1){
  25.             f[i+a] = max(f[i+a], f[i] + 1);
  26.             f[i+b] = max(f[i+b], f[i] + 1);
  27.             f[i+c] = max(f[i+c], f[i] + 1); 
  28.         }
  29.        */
  30.     }
  31.     cout << f[s];
  32.  
  33.  
  34.  
  35.  
  36.  
  37.  
  38.  
  39.     return 0;
  40. }
  41.  
  42.  
  43.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/NUl5m5
language:
C++14 (gcc 8.3)
created:
1 hour 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!