http://www.cnblogs.com/AOQNRMGYXLMV/p/4934747.html
#include<iostream>
#include<cstdio>
#include<algorithm> using namespace std;
const int maxn=;
const int inf=0x3f3f3f3f;
int a[maxn];
int b[maxn];
int val[]={,,,,,,,,,};
int Solve(int t)
{
int ans=;
for(int i=;i>=;i--)
{
if(i==||i==)
{
int cnt=min(t/(val[i]*),b[i]/);
ans+=cnt*;
t-=val[i]**cnt;
}
else
{
int cnt=min(t/val[i],b[i]);
ans+=cnt;
t-=val[i]*cnt;
}
if(t==)
{
break;
}
}
if(t==)
{
return ans;
}
else
{
return inf;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int p;
scanf("%d",&p);
int tot=;
int sum=;
for(int i=;i<;i++)
{
scanf("%d",&a[i]);
tot+=a[i];
sum+=val[i]*a[i];
}
if(sum<p)
{
printf("-1\n");
continue;
}
p=sum-p;
int ans=inf;
for(int i=;i<;i++)
{
for(int k=;k<;k++)
{
int temp=p;
memcpy(b,a,sizeof(a));
if(i)
{
if(b[])
{
temp-=val[];
b[]--;
}
else
{
continue;
}
}
if(k)
{
if(b[])
{
temp-=val[];
b[]--;
}
else
{
continue;
}
}
if(temp>=)
{
ans=min(ans,Solve(temp)+i+k);
}
}
}
if(ans==inf)
{
printf("-1\n");
}
else
{
printf("%d\n",tot-ans);
}
}
return ;
}
考虑问题的反面，求最大转化为求剩余的最小。然后从大到小贪心，能多用大面值的尽量多用。特判20,50；200,500