刘如佳书p164--硬币问题

#include<cstdlib>#include<iostream>#include<cstdio>#include<cmath>#include<set>#include<cstring>#include <algorithm>#define inf 0x7fffffff#define N 1000#define MIN 1e-11#define M 100#define LL long longusing namespace std;int n,k,h,t,m;int a[N],d[N];int dfsmin(int s){    int &ans=d[s];    if(ans!=-1)return ans;    ans=inf-1000;//返回后加1会变成负值！    for(int i=0; i<n; i++)        if(s>=a[i])            ans=min(ans,dfsmin(s-a[i])+1);    return ans;}int dfsmax(int s){    int &ans=d[s];    if(ans!=-1)return ans;    ans=-inf;    for(int i=0; i<n; i++)        if(s>=a[i])            ans=max(ans,dfsmax(s-a[i])+1);    return ans;}void printmin(int s){    for(int i=0; i<n; i++)        if(s>=a[i]&&d[s]==d[s-a[i]]+1)        {            printf("%d ",a[i]);            printmin(s-a[i]);            break;        }}void printmax(int s){    for(int i=0; i<n; i++)        if(s>=a[i]&&d[s]==d[s-a[i]]+1)        {            printf("%d ",a[i]);            printmax(s-a[i]);            break;        }}int main(){#ifndef ONLINE_JUDGE    freopen("ex.in","r",stdin);#endif//intput example：//5//2 5 7 10 20//3//22//100    int s;    scanf("%d",&n);    for(int i=0; i<n; ++i)        scanf("%d",&a[i]);    while(scanf("%d",&s)!=EOF)    {        memset(d,-1,sizeof(d));        d[0]=0;        int minv=dfsmin(s);        printf("minv=%d        \n",minv);        if(minv<1000)            printmin(s);        cout<<endl;        memset(d,-1,sizeof(d));        d[0]=0;        int maxv=dfsmax(s);        printf("maxv=%d        \n",maxv);        if(maxv>0)            printmax(s);        cout<<endl;    }    return 0;}