DTDOI - Đổi tiền
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
using namespace std;
#define MAX 100000
int n, s;
int a[111];
int F[MAX + 10];
int main() {
scanf("%d%d", &n, &s);
for(int i=0;i<n;++i) scanf("%d", a + i);
memset( F, 0x1f, sizeof(F));
F[0] = 0;
for(int i=0;i<MAX;++i) {
for(int j=0;j<n;++j)
if(i + a[j] <= MAX)
F[i + a[j]] <?= F[i] + 1;
}
if(s <= MAX) cout << F[s] << endl;
else {
int best = 1000000000;
for(int i=0;i<MAX;++i)
for(int j=0;j<n;++j)
if((s - i) % a[j] == 0)
best <?= F[i] + (s - i) / a[j];
cout << best << endl;
}
// system("pause");
return 0;
}