UVA_10626

    实际上我们注意到硬币的总状态不是很多，约是500*100*50（当然这么说并不准确，后面会再算），所以我们可以把硬币的组合形式看成一个状态。

    剩下的问题就是如何转移状态，我们细算一下，发现花钱的策略不过这么几种，如果再分细一些，可以先分成有找零的和没找零的：①8个1分的；②3个1分的和1个5分的；③2个5分的找回2个1分的；④一个10分的找回2个1分的；⑤3个1分的和1个10分的找回1个5分的。其余的可能也有，但一定不会比上面五种决策更优。

    显然递推是不好搞的，所以就不妨记忆化搜索吧。但注意到，我们按上面的策略花钱时，有些硬币是会增加的，所以我们要把上限算好。首先，③和④会增加1分的数量，最多增加的数量不会超过200个，其次⑤会增加5分的数量，但不会超过50个，于是开个710*160*60的数组即可。

#include
     
       #include
      
        #define INF 1000000000 int f[710][160][60], C, N, X, Y, Z; int dp(int n1, int n5, int n10) {
   int i, j, k, min = INF; if(f[n1][n5][n10] != -1) return f[n1][n5][n10]; if(n1 + n5 * 5 + n10 * 10 == N) return f[n1][n5][n10] = 0; if(n1 >= 3 && n5 >= 1)     {
           k = dp(n1 - 3, n5 - 1, n10); if(k + 4 < min)             min = k + 4;     } if(n5 >= 2)     {
           k = dp(n1 + 2, n5 - 2, n10); if(k + 2 < min)             min = k + 2;     } if(n1 >= 3 && n10 >= 1)     {
           k = dp(n1 - 3, n5 + 1, n10 - 1); if(k + 4 < min)             min = k + 4;     } if(n10 >= 1)     {
           k = dp(n1 + 2, n5, n10 - 1); if(k + 1 < min)             min = k + 1;     } if(n1 >= 8)     {
           k = dp(n1 - 8, n5, n10); if(k + 8 < min)             min = k + 8;     } return f[n1][n5][n10] = min; } void solve() {
   int res;     scanf("%d%d%d%d", &C, &X, &Y, &Z);     N = X + 5 * Y + 10 * Z - C * 8;     memset(f, -1, sizeof(f));     res = dp(X, Y, Z);     printf("%d\n", res); } int main() {
   int t;     scanf("%d", &t); while(t --)     {
           solve();     } return 0; }