poj3181【完全背包+整数拆分】 poj3181【完全背包+整数拆分】

题意：
给你一个数n,在给你一个数K,问你这个n用1-k的数去组合，有多少种组合方式。
思路：
背包重量就是n；
那么可以看出 1-k就是重物，价值是数值，重量是数值。
每个重物可以无限取，问题转化为完全背包。
我们用dp[]代表方案数的话，dp[0]=1;
由于当n=1000，k=1000的时候这个方案数是巨大的。
看了别的大牛博客，这个整数拆分真是好啊；
一个代表高位，一个代表低位；

#include #include #include #include using namespace std; typedef long long LL; const LL INF=1e18; const int N=1e3+10; LL d1[N],d2[N]; int main() { int n,k; scanf("%d%d",&n,&k); memset(d1,0,sizeof(d1)); memset(d2,0,sizeof(d2)); d2[0]=1; for(int i=1; i<=k; i++) { for(int j=i; j<=n; j++) { d1[j]=d1[j]+d1[j-i]+(d2[j]+d2[j-i])/INF; //高位 d2[j]=(d2[j]+d2[j-i])%INF; } } if(d1[n]) printf("%lld",d1[n]); printf("%lld\n",d2[n]); return 0; }

【poj3181【完全背包+整数拆分】】转载于:https://www.cnblogs.com/keyboarder-zsq/p/5934894.html