UVa 10626 - Buying Coke
传送门
题意
我们要买C瓶可乐，每瓶8元，有XYZ个1、5、10的硬币，可以找钱，求所用最小硬币数。
思路
可以按照找不找钱分类，找钱又分为找多少钱。
不找钱的时候，可以分为$8 1, 3 1 + 5$。
找2块，$5 2, 10 1$，找5块，$3 * 1 + 10$。
代码
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int dp[710][160][60], remain;
int DFS(int n1, int n5, int n10)
{
int &cur = dp[n1][n5][n10];
if (cur != -1)
return cur;
if (n1 + n5 * 5 + n10 * 10 == remain)
return cur = 0;
cur = INF;
if (n1 >= 8)
cur = min(DFS(n1 - 8, n5, n10) + 8, cur);
if (n1 >= 3 && n5 >= 1)
cur = min(DFS(n1 - 3, n5 - 1, n10) + 4, cur);
if (n1 >= 3 && n10 >= 1)
cur = min(DFS(n1 - 3, n5 + 1, n10 - 1) + 4, cur);
if (n5 >= 2)
cur = min(DFS(n1 + 2, n5 - 2, n10) + 2, cur);
if (n10 >= 1)
cur = min(DFS(n1 + 2, n5, n10 - 1) + 1, cur);
return cur;
}
int main()
{
int C, n1, n5, n10, i, j, T;
scanf("%d", &T);
while (T--)
{
memset(dp, -1, sizeof dp);
scanf("%d%d%d%d", &C, &n1, &n5, &n10);
remain = n1 + n5 * 5 + n10 * 10 - C * 8;
printf("%d\n", DFS(n1, n5, n10));
}
return 0;
}