3680229_ac_0ms_184k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int v[] = {25, 10, 5, 1};

struct Node
{
	int cnt[4];

	Node()
	{
		memset(cnt, 0, sizeof(cnt));
	}
	Node inc(int pos)
	{
		this->cnt[pos]++;
		Node ret = (*this);
		this->cnt[pos]--;
		
		return ret;
	}
};

Node sol[100];
int best[100];
int cnt[4];
int tot;

void dp()
{
	int i, j, k;

	memset(best, -1, sizeof(best));
	best[0] = 0;
	sol[0] = Node();
	for (j = 0; j < 4; j++)
	{
		for (i = 1; i <= cnt[j]; i++)
		{
			for (k = tot - v[j]; k >= 0; k--)
			{
				if (best[k] != -1)
				{
					if (best[k + v[j]] == -1 || best[k + v[j]] > best[k] + 1)
					{
						best[k + v[j]] = best[k] + 1;
						sol[k + v[j]] = sol[k].inc(j);
					}
				}
			}
		}
	}
	if (best[tot] == -1)
		puts("Cannot dispense the desired amount.");
	else
		printf("Dispense %d quarters, %d dimes, %d nickels, and %d pennies.\n", sol[tot].cnt[0], sol[tot].cnt[1], sol[tot].cnt[2], sol[tot].cnt[3]);
}

int main()
{
	while (scanf("%d%d%d%d%d", &cnt[0], &cnt[1], &cnt[2], &cnt[3], &tot) == 5)
	{
		if (cnt[0] == 0 && cnt[1] == 0 && cnt[2] == 0 && cnt[3] == 0 && tot == 0)
		{
			break;
		}
		dp();
	}
	return 0;
}