DTDOI - Đổi tiền
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
#define MAX 111
using namespace std;
const int mdp=60000;
int n,s,mv;
int v[MAX];
int f[MAX][mdp];
void init(void) {
scanf("%d",&n);
scanf("%d",&s);
int i;
mv=-1;
for (i=1;i<=n;i=i+1) {
scanf("%d",&v[i]);
if (v[i]>mv) mv=v[i];
}
sort(&v[1],&v[n+1]);
}
int min(const int &x,const int &y) {
if (x<y) return (x); else return (y);
}
void optimize(void) {
int i,j;
for (i=1;i<=n;i=i+1) f[i][0]=0;
for (i=1;i<mdp;i=i+1) f[1][i]=i;
for (i=2;i<=n;i=i+1)
for (j=1;j<mdp;j=j+1) {
if (j<v[i]) f[i][j]=f[i-1][j];
else f[i][j]=min(f[i-1][j],f[i][j-v[i]]+1);
}
}
void answer(void) {
if (s<mdp) {
printf("%d",f[n][s]);
return;
}
int i;
int best=(int)1e9;
for (i=s/mv;i>=0;i=i-1) {
if (s-mv*i>=mdp) break;
best=min(best,i+f[n][s-mv*i]);
}
printf("%d",best);
}
int main(void) {
init();
optimize();
answer();
return 0;
}