POJ 3181 Dollar Dayz（高精度 动态规划）

题目链接：http://poj.org/problem?id=3181

题目大意：用1,2...K元的硬币，凑成N元的方案数。

Sample Input

5 3

Sample Output

5

分析：这不是母函数是什么，不管你信不信，反正我是信了。

　　之前有过一篇，讲母函数的动态规划做法http://www.cnblogs.com/acm-bingzi/archive/2013/04/30/3051725.html

　　这道题目，坑就坑在高精度上了，刚开始怎么也没想到，而且做法也很奇特。就是将2个long long 的数字进行拼接。

代码如下：

# include<stdio.h>
# include<string.h>
# define maxn 1005
long long int a[maxn],b[maxn],inf;
int n,k;
int main(){
    int i,j;
    while(scanf("%d%d",&n,&k)!=EOF){
        for(inf=1,i=0;i<18;i++)
            inf *= 10;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        a[0] = 1;
        for(j=1;j<=k;j++)
            for(i=1;i<=n;i++)
                if(i >= j) {
                    b[i] = b[i] + b[i-j] + (a[i]+a[i-j])/inf;
                    a[i] = (a[i]+a[i-j])%inf;
                } 
                if(b[n])
                    printf("%lld",b[n]);
                printf("%lld
",a[n]);
    }
    return 0;
}