首页 > 代码库 > uva10626 - Buying Coke(记忆话搜索)

uva10626 - Buying Coke(记忆话搜索)

题目:uva10626 - Buying Coke(记忆话搜索)


题目大意:给你3种价值的硬币, 1, 5, 10现在要求你取自动售卖机买可乐,一瓶可乐价值8,给你要求买的可乐的数目,和三种硬币的数目,问你最少需要投多少硬币。自动售卖机会根据你投入的钱来找零,可以的话找出的零钱硬币会最少。


解题思路: 这题之前没有想到可乐的已经购买瓶数是隐含在剩余的硬币情况中,换句话说就是你买了多少瓶可乐,不论用什么方式买,剩余的硬币的情况总能反映买了多少瓶可乐。所

以数组开3维就可以了。而且要注意还有 1 个 10 和 3 个1 买 1 coke 找 1个 5的情况。 转移状态(2 个 5 找 2个 1) ( 1个10 找 2个1 ) (1个5 3个1 找 0) (1个10 3个 1 找1 个5)最后的8个1 可以放在最后考虑,因为是最坏的情况才用这个,所以当5和10的硬币都没有了,再用1来买。


代码:

#include <cstdio>
#include <cstring>

const int N1 = 705;
const int N2 = 155;
const int N3 = 55;
const int INF = 0x3f3f3f3f;

int f[N1][N2][N3];

void init () {

	for (int i = 0; i < N1; i++)
		for (int k = 0; k < N2; k++)
			for (int l = 0; l < N3; l++)
				f[i][k][l] = INF;
}

int Min (const int a, const int b) { return a < b? a: b;}

int DP (int c, int n1, int n2, int n3) {

//	printf ("%d %d %d %d\n", c, n1, n2, n3);
	int& ans = f[n1][n2][n3];
	if (ans != INF)
		return ans;
	if (c == 0) 
		return ans = 0;

	if (!n2 && !n3) 
		return ans = 8 * c;

	if (n3) 	
		ans = Min (ans, DP(c - 1, n1 + 2, n2, n3 - 1) + 1);
	if (n2 >= 2) 
		ans = Min (ans, DP(c - 1, n1 + 2, n2 - 2, n3) + 2);
	if (n2 && n1 >= 3)
		ans = Min (ans, DP(c - 1, n1 - 3, n2 - 1, n3) + 4);
	if (n3 && n1 >= 3)
		ans = Min (ans, DP(c - 1, n1 - 3, n2 + 1, n3 - 1) + 4);
	return ans;
}

int main () {

	int t;
	int c, n1, n2, n3;
	scanf ("%d", &t);
	while (t--) {

		scanf ("%d%d%d%d", &c, &n1, &n2, &n3); 
		init ();
		printf ("%d\n", DP(c, n1, n2, n3));
	}
	return 0;
}


uva10626 - Buying Coke(记忆话搜索)