首页 > 代码库 > HDU 2069
HDU 2069
把多项式变成二维的即可,设c[i][j]为i枚硬币下j元的组合数。(因为限定不能超过100个硬币)。然后就是普通的生成函数的题了。
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#define N 260using namespace std;int c1[N][N],c2[N][N];int Fa[N];int main(){ int n,sum; Fa[1]=1,Fa[2]=5,Fa[3]=10,Fa[4]=25,Fa[5]=50; memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); for(int i=0;i<101;i++) c1[i][i]=1; for(int i=2;i<=5;i++){ for(int j=0;j<101;j++){ for(int k=0;k<N;k++){ for(int p=0;p+k<N;p+=Fa[i]){ c2[j+p/Fa[i]][p+k]+=c1[j][k]; } } } for(int j=0;j<101;j++) for(int k=0;k<N;k++) c1[j][k]=c2[j][k],c2[j][k]=0; } while(scanf("%d",&n)!=EOF){ int ans=0; for(int i=0;i<=100;i++) ans+=c1[i][n]; printf("%d\n",ans); } return 0;}
HDU 2069
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。