首页 > 代码库 > Hdu 2566 统计硬币
Hdu 2566 统计硬币
Problem地址：http://acm.hdu.edu.cn/showproblem.php?pid=2566
看完这题，这不禁让我想起了hdu的2069。
两者同样是求有多少种方法，没有要求说明具体的组合方式，因此可以采用生成函数的方法解题。
可以采用一个二维数组，同时控制硬币的总数量及总价值，其数组某一元素的值为在此数量和总价下的组合方式。
因此可以采用先打表的方式。
#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int MAXN = 700;int c1[MAXN][MAXN], c2[MAXN][MAXN];int coin[3] = {1,2,5};int main(){ int i,j,k,l; int loop; int N,M; memset( c1, 0, sizeof(c1) ); memset( c2, 0, sizeof(c2) ); for( i=0;i<MAXN;i++ ) c1[i][i] = 1; for( i=1;i<3;i++ ) // the value of coins { for( j=0;j<MAXN;j++ ) // the num of former coins { for( l=0;l<MAXN;l++ ) // the value of former coins { for( loop=0;loop*coin[i] + l<MAXN && j+loop<MAXN;loop++ ) { c2[ j+loop ][ loop*coin[i]+l ] += c1[j][l]; } } } for( j=0;j<MAXN;j++ ) { for( k=0;k<MAXN;k++ ) { c1[j][k] = c2[j][k]; c2[j][k] = 0; } } } int T; cin >> T; while( T-- ) { cin >> N >> M; cout << c1[N][M] << endl; } return 0;}
Hdu 2566 统计硬币
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。