ECNU动态规划专题训练(ing)
分析: 先完全背包预处理出所有的 整数倍票价 ( 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;
} 
传音控股晋升空间 51人发布
