首页 > 代码库 > hdu 1398 Square Coins(母函数,完全背包)
hdu 1398 Square Coins(母函数,完全背包)
链接:hdu 1398
题意:有17种货币,面额分别为i*i(1<=i<=17),都为无限张,
给定一个值n(n<=300),求用上述货币能使价值总和为n的方案数
分析:这题可以用母函数的思想,对300以内的值进行预处理即可
也可用完全背包思想求300以内的方案数
母函数:
#include<stdio.h> int main() { int c1[305],c2[305],i,j,k,n; for(i=0;i<=300;i++){ c1[i]=1; c2[i]=0; } for(i=2;i<=17;i++){ for(j=0;j<=300;j++) for(k=0;j+k<=300;k+=i*i) //这里每次累加i*i,因为第i种货币面额为i*i c2[j+k]+=c1[j]; for(j=0;j<=300;j++){ c1[j]=c2[j]; c2[j]=0; } } while(scanf("%d",&n)!=EOF){ if(n==0) break; printf("%d\n",c1[n]); } return 0; }
完全背包
#include<stdio.h> int main() { int a[20]={0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289},f[305]={0}; int i,n,j; f[0]=1; for(i=1;i<=17;i++) for(j=a[i];j<=300;j++) f[j]+=f[j-a[i]]; while(scanf("%d",&n)!=EOF){ if(n==0) break; printf("%d\n",f[n]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。