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;
}

Download