分析: 先完全背包预处理出所有的 整数倍票价 ( t * p ) 最少需要多少张纸币,问题就转化为另一个完全背包
code :
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int a[7]={1,5,10,20,50,100}; int c[maxn],f[1004]; int main() { int n,p,k; scanf("%d%d%d",&n,&k,&p); for(int i=0;i<=n*p;i++) c[i]=f[i]=1e9; c[0]=f[0]=0; for(int i=0;i<6;i++) for(int j=a[i];j<=n*p;j++) c[j]=min(c[j],c[j-a[i]]+1); for(int i=1;i<=k;i++) for(int j=i;j<=n;j++) f[j]=min(f[j],f[j-i]+c[i*p]); printf("%d",f[n]); return 0; }