Rikka with Coin(暴力)

題目連結：HDU 6685

題意：

有4種硬币：10,20,50,100 ，每種無限個，現在你要挑選最少的個數，使得可以組成給出的n個價格。

解法：

觀察下就不難發現，10元的最多取10個，20元的最多取5個，50元的最多取2個，看出這個結論後就很簡單了，暴力預處理打下表，has[a][b][c][x]代表10元取a個，20元取b個，50元取c個是否能組成x。枚舉10元20元30元的個數，如果不夠的話就用100元來湊，取個最小值就是答案了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool has[11][6][3][33];
bool check(int x,int a,int b,int c)//50 20 10
{
    for(int i=0;i<=a;i++)
    {
        for(int j=0;j<=b;j++)
        {
            int rest=x-i*5-j*2;
            if(rest<=c&&rest>=0) return 1;
        }
    }
    return 0;
}
const int N=500;
#define inf 0x3f3f3f3f
int A[N];
int main()
{
    for(int i=0;i<=10;i++)//6重循環打表（暴力大法好啊！！）
    {
        for(int j=0;j<=5;j++)
        {
            for(int k=0;k<=2;k++)//
            {
                for(int x=0;x<=30;x++)
                {
                    has[i][j][k][x]=check(x,k,j,i);
                }
            }
        }
    }
    int T;scanf("%d",&T);
    while(T--)
    {
        int n;scanf("%d",&n);
        int flag=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&A[i]);
            if(A[i]%10) flag=1;//把不能組成的情況先判了
        }
        if(flag)
        {
            printf("-1\n");
            continue;
        }
        int ans=inf;
        for(int a=0;a<=10;a++)//枚舉a b c求最小答案
        {
            for(int b=0;b<=5;b++)
            {
                for(int c=0;c<=2;c++)
                {
                    int s=0,flag=1;
                    for(int i=1;i<=n;i++)
                    {
                        int mod=A[i]%100,tmp=inf;
                        for(int x=0;x<=3;x++)
                        {
                            if(A[i]>=x*100&&x*100+mod<=300)
                            {
                                A[i]-=x*100;
                                if(has[a][b][c][mod/10+x*10])
                                {
                                    tmp=min(tmp,A[i]/100);
                                }
                                A[i]+=x*100;
                            }
                        }
                        if(tmp==inf) flag=0;
                        s=max(s,tmp);
                    }
                    if(flag)
                    {
//                        printf("%d\n",s);
                         ans=min(ans,a+b+c+s);
                    }

                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
           

後面發現枚舉的範圍似乎不需要這麼大。。。。。。。