首页 > 代码库 > 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