USACO 3.1.6 – Stamps

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
	freopen("stamps.in", "r", stdin), freopen("stamps.out", "w", stdout);
	int MAX= 2000001, j, K, N, i , coins[51];
	unsigned char count[2000001] = {0};
	scanf("%d %d", &K, &N);
	for (i = 0; i < N; i++) scanf("%d", coins+i);
	
	for(i=1, count[1]=201; i<MAX; i++, count[i]=201)
		for(j=0; j<N ; j++)
			if(i>=coins[j])
				count[i] = min(int(count[i]), int(count[i-coins[j]])+1);
	
	for(i=1; count[i]<=K; i++)
		;

	printf("%d\n", i-1);
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: