题目大意：给出要买可乐的数量， 以及1元，5元和10元硬币的数量， 每瓶可乐8元，每次照钱会按照最少硬币的方式找回， 问如何投币可使得投入的硬币数最少， 输出最少硬币值。
解题思路：记忆化搜索， 因为可乐每购买一次便要找会硬币，所以对与每个状态考虑的情况比并不是很多。
注意：1、每够买一次可乐便会找回一次硬币，所以不用考虑的太复杂。
2、题目中虽然说1元不超过500个，但是开的记录数组一定要比500大，大约700左右，因为要考虑找回金额的情况。
#include <stdio.h>
#include <string.h>
#define min(a,b) (a) < (b) ? (a) : (b)
const int MAX = 1 << 30; int vis[705][205][105], dp[705][205][105]; int solve(int c, int n1, int n5, int n10) {
int&cnt = dp[n1][n5][n10];
int& flag = vis[n1][n5][n10];
if (flag) return cnt;
else if (c == 0) {
flag = 1;
cnt = 0;
return cnt;
}
else {
cnt = MAX;
if (n1 >= 8) cnt = min(cnt, solve(c - 1, n1 - 8, n5, n10) + 8);
if (n5 >= 1 && n1 >= 3) cnt = min(cnt, solve(c - 1, n1 - 3, n5 - 1, n10) + 4);
if (n5 >= 2) cnt = min(cnt, solve(c - 1, n1 + 2, n5 - 2, n10) + 2);
if (n10 >= 1) cnt = min(cnt, solve(c - 1, n1 + 2, n5, n10 - 1) + 1);
if (n10 >= 1 && n1 >= 3) cnt = min(cnt, solve(c - 1, n1 - 3, n5 + 1, n10 - 1) + 4);
flag = 1;
return cnt;
}
} int main() {
int cas;
scanf("%d", &cas);
while (cas--) {
int c, n1, n5, n10;
scanf("%d%d%d%d", &c, &n1, &n5, &n10);
memset(vis, 0, sizeof(vis));
printf("%d\n", solve(c, n1, n5, n10));
}
return 0;
}