UVA147 Dollars

传送门

这是一道背包题。

首先我们可以发现数据有小数但范围很小，所以我们可以将其直接乘为整数。又发现最小的钱的价值为 $5$，且其他的价值都是他的倍数，所以可以再整体除去这个数，同时缩小数据范围，避免不必要的空间浪费。

由于数据范围非常小，我们可以预处理出所有情况，输出即可。同时这道题细节也要注意。

细节一

要将读入的小数先数出来并且保留两位小数，在宽度为 $6$ 的字段中右对齐。下一行是可能组成该组数据的方法数，在宽度为 $17$ 的字段中右对齐。所以可以用 printf 输出。

细节二

注意给存结果的数组赋初值。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
double a;
int m;
int a_a[]={2000,1000,400,200,100,40,20,10,4,2,1};//全部除5 
long long ans[6001];//最大值范围也除5，节省空间 
int main(){
  ans[0]=1;//赋初值 
  for(int i=0;i<=10;i++)//共11种金钱面额 
    for(int j=a_a[i];j<=6000;j++)
      ans[j]+=ans[j-a_a[i]];//预处理出每种情况 
  while(1){
    cin>>a;
    if(a==0)break;
    printf("%6.2lf",a);//注意输出格式 
    m=a*20;//a*100/5=a*20
    printf("%17lld\n",ans[m]);//注意输出格式
  }
  return 0;
}