POJ1252 Euro Efficiency

On January 1st 2002, The Netherlands, and several other European countries abandoned their national currency in favour of the Euro. This changed the ease of paying, and not just internationally.
A student buying a 68 guilder book before January 1st could pay for the book with one 50 guilder banknote and two 10 guilder banknotes, receiving two guilders in change. In short:50+10+10-1-1=68. Other ways of paying were: 50+25-5-1-1, or 100-25-5-1-1.Either way, there are always 5 units (banknotes or coins) involved in the payment process, and it
could not be done with less than 5 units.
Buying a 68 Euro book is easier these days: 50+20-2 = 68, so only 3 units are involved.This is no coincidence; in many other cases paying with euros is more efficient than paying with guilders. On average the Euro is more efficient. This has nothing to do, of course, with the value of the Euro, but with the units chosen. The units for guilders used to be: 1, 2.5, 5, 10, 25, 50,whereas the units for the Euro are: 1, 2, 5, 10, 20, 50.
For this problem we restrict ourselves to amounts up to 100 cents. The Euro has coins with values 1, 2, 5, 10, 20, 50 eurocents. In paying an arbitrary amount in the range [1, 100] eurocents, on average 2.96 coins are involved, either as payment or as change. The Euro series is not optimal in this sense. With coins 1, 24, 34, 39, 46, 50 an amount of 68 cents can be paid using two coins.The average number of coins involved in paying an amount in the range [1, 100] is 2.52.
Calculations with the latter series are more complex, however. That is, mental calculations.These calculations could easily be programmed in any mobile phone, which nearly everybody carries around nowadays. Preparing for the future, a committee of the European Central Bank is studying the efficiency of series of coins, to find the most efficient series for amounts up to 100 eurocents. They need your help.
Write a program that, given a series of coins, calculates the average and maximum number of coins needed to pay any amount up to and including 100 cents. You may assume that both parties involved have sufficient numbers of any coin at their disposal.

Input

The first line of the input contains the number of test cases. Each test case is described by 6 different positive integers on a single line: the values of the coins, in ascending order. The first number is always 1. The last number is less than 100.

Output

For each test case the output is a single line containing first the average and then the maximum number of coins involved in paying an amount in the range [1, 100]. These values are separated by a space. As in the example, the average should always contain two digits behind the decimal point. The maximum is always an integer.

Sample Input

3
1 2 5 10 20 50
1 24 34 39 46 50
1 2 3 7 19 72

Sample Output

2.96 5
2.52 3
2.80 4

题目大意给6种不同面额硬币，求组成[1,100]中数的平均需要硬币与最多需要硬币数，

可以通过减法获得，比如有1、4两种硬币，凑成3可以用4-1两个硬币完成，
而不是1+1+1三个硬币。

乍一看，很水的题，DP做得话要注意两点：
一：题目不仅仅有+的操作，也有哦-的操作，网上大佬们的代码一个数组就ok，为了方便理解，我开的是两个数组，对于初学者更好理解。
二：题目dp不能只开到100.。而是要开大点，到2000足以。。因为我们假设。。存在1、95、96、97、98、99这样又大又互质的数据。。那么算的话会算到很大的数，网上说开2000，可是我两千wa了几次，后来开了10100的数组才AC了
三：由于笔者并不熟悉c的输入输出，图方便用了，结果wa了几次，后来无意之中看到有人也错在同一个地方，发现是定义的是float型，输出了“%0.2lf”，改成“%0.2f”果断AC。到现在也没想懂。
AC代码如下：（适和dp入门的新手看）

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF  99999999
#define min(a,b)  (a>b? b:a)
#define max(a,b)  (a>b? a:b)
using namespace std;
int dp1[10100],dp2[10100];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int val[10];
        for(int i=1;i<=6;i++)
            cin>>val[i];
        for(int i=0;i<=10100;i++)
            dp1[i]=dp2[i]=INF;
        dp1[0]=dp2[0]=0;
        for(int i=1;i<=6;i++)
        {
            for(int j=val[i];j<=10000;j++)
            {
                dp1[j]=min(dp1[j],dp1[j-val[i]]+1);
            }
        }
        for(int i=1;i<=6;i++)
        {
            for(int j=val[i];j<=10000;j++)
                dp2[j]=min(dp2[j],dp2[j-val[i]]+1);
        }
        int ans[200];
        for(int i=1;i<=100;i++)
            ans[i]=INF;
        for(int i=1;i<=100;i++)
        {
            for(int j=0;j<=10000;j++)
            {
                ans[i]=min(ans[i],dp1[i+j]+dp2[j]);
                ans[i]=min(ans[i],dp1[i]);
            }
        }
        float average=0;
        int mx=0;
        for(int i=1;i<=100;i++)
        {
            average+=ans[i];
            mx=max(mx,ans[i]);
        }
        printf("%.2f %d\n",average/100,mx);
    }
    return 0;
}