UVA 147 - Dollars

[DP]

空間尚可省

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
#define DOL 11
#define LL long long int
int dollars[DOL]={5,10,20,50,100,200,500,1000,2000,5000,10000};
LL Table[DOL][30010];
LL getTable(int type,int money)
{
    if(money<0) return 0;
    if(money==0) return 1;
    if(type<0) return 0;
    return Table[type][money];
}
int main()
{
    memset(Table,0,sizeof(Table));
    for(int lx=0;lx<DOL;lx++)
        for(int ly=1;ly<=30000;ly++)
            Table[lx][ly]=getTable(lx-1,ly)+getTable(lx,ly-dollars[lx]);
/*  for(int ly=0;ly<=30;ly++)
    {
        for(int lx=0;lx<5;lx++)
            printf("%lld\t",getTable(lx,ly));
        printf("\n");
    }*/
    int m1,m2;
    while((scanf("%d.%d",&m1,&m2)!=EOF)&&(m1+m2))
        printf("%3d.%02d%17lld\n",m1,m2,getTable(DOL-1,m1*100+m2));
    return 0;
}