题目链接: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; }