Problem D
Buying Coke 
Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

I often buy Coca-Cola from the vending machine at work. Usually I buy several cokes at once, since my working mates also likes coke. A coke in the vending machine costs 8 Swedish crowns, and the machine accept crowns with the values 1, 5 and 10. As soon as I press the coke button (after having inserted sufficient amount of money), I receive a coke followed by the exchange (if any). The exchange is always given in as few coins as possible (this is uniquely determined by the coin set used). This procedure is repeated until I‘ve bought all the cokes I want. Note that I can pick up the coin exchange and use those coins when buying further cokes.

Now, what is the least number of coins I must insert, given the number of cokes I want to buy and the number of coins I have of each value? Please help me solve this problem while I create some harder problems for you. You may assume that the machine won‘t run out of coins and that I always have enough coins to buy all the cokes I want.

Input

The first line in the input contains the number of test cases (at most 50). Each case is then given on a line by itself. A test case consists of four integers: C (the number of cokes I want to buy), n₁, n₅, n₁₀ (the number of coins of value 1, 5 and 10, respectively). The input limits are 1 <= C <= 150, 0 <= n₁ <= 500, 0 <= n₅ <= 100 and 0 <= n₁₀ <= 50.

Output

For each test case, output a line containing a single integer: the minimum number of coins needed to insert into the vending machine.

Sample Input                               Output for Sample Input

3

2 2 1 1

2 1 4 1

20 200 3 0

5

3

148

Problem setter: Jimmy M?rdell, Member of Elite Problemsetters‘ Panel

题目大意：

去买可乐，一瓶可乐8元。有1元、5元和10元三种货币，初始分别拥有数量给定。自动售货机会用最少的硬币数量找零。找零的钱可以继续使用。问最少向售货机中投入多少枚硬币，能买到C瓶可乐。

解题思路：

货币数量较少，状态不多。只有付10*1找1*2（投入1枚）、付5*1+1*3找0（投入4枚）、付10*1+1*3找5*1（投入4枚）、付1*8找0（投入8枚）这四种情况，可以想到其他的方法，投入的硬币数量肯定更多，所以不用考虑。

动态规划。只需记录三种面值的数量所为状态即可。用dp[n1][n5][n10]表示还有n1枚1元、n5枚5元、n10枚10元硬币状态下的投入硬币数。

状态转移方程：dp[n1][n5][n10] = min( dp[n1+2][n5][n10-1] + 1,  dp[n1-3][n5-1][n10] + 4, dp[n1-3][n5+1][n10-1] + 4 , dp[n1-8][n5][n10] + 8 );

参考代码：

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

const int MAX1 = 710, MAX5 = 110, MAX10 = 60;
const int INF = 0x3f3f3f3f;
int nCase, c, n1, n5, n10, dp[MAX1][MAX5][MAX10];

void init() {
    memset(dp, -1, sizeof(dp));
}

void input() {
    scanf("%d%d%d%d", &c, &n1, &n5, &n10);
}

int DP(int c, int n1, int n5, int n10) {
    if (c == 0) return 0;
    if (dp[n1][n5][n10] != -1) return dp[n1][n5][n10];

    int ret = INF;
    if (n10 >= 1) {
        ret = min(ret, DP(c-1, n1+2, n5, n10-1) + 1);
    }
    if (n5 >= 2) {
        ret = min(ret, DP(c-1, n1+2, n5-2, n10) + 2);
    }
    if (n5 >= 1 && n1 >= 3) {
        ret = min(ret, DP(c-1, n1-3, n5-1, n10) + 4);
    }
    if (n10 >= 1 && n1 >= 3) {
        ret = min(ret, DP(c-1, n1-3, n5+1, n10-1) + 4);
    }
    if (n1 >= 8) {
        ret = min(ret, DP(c-1, n1-8, n5, n10) + 8);
    }
    return dp[n1][n5][n10] = ret;
}

void solve() {
    printf("%d\n", DP(c, n1, n5, n10));
}

int main() {
    scanf("%d", &nCase);
    while (nCase--) {
        init();
        input();
        solve();
    }
    return 0;
}

UVa 10626 Buying Coke（DP）