题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1028
题目大意:题目问一个数字n能够拆成多少种数字的和
可以背包搞,直接生成函数模板题。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

struct Function{
    int n1[1005], n2[1005], v[1005];
    int a[1005], b[1005];
    int getfun(int k, int p){
        memset(a, 0, sizeof(int)*(p+1));
        a[0]=1;
        int last=0;
        for(int i=1; i<=k; i++){
            int last2=min(last+n2[i]*v[i], p);
            memset(b, 0, sizeof(int)*(last2+1));
            for(int j=n1[i]; j<=n2[i]&&j*v[i]<=last2; j++){
                for(int k=0; k<=last&&k+j*v[i]<=last2; k++){
                    b[k+j*v[i]]+=a[k];
                }
            }
            memcpy(a, b, sizeof(int)*(last2+1));
            last=last2;
        }
        return a[p];
    }
}fun;

int main() {

    for(int i=1; i<=125; i++){
        fun.v[i]=i, fun.n1[i]=0, fun.n2[i]=125;
    }
    fun.getfun(125, 125);
    int n;
    while(~scanf("%d", &n)){
        printf("%d\n", fun.a[n]);
    }

    return 0;
}