刘如佳书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;}