本文共 735 字，大约阅读时间需要 2 分钟。
这道题似乎还可以用母函数做出来，不过当时懒得思考，就直接用DP做了。
其实这是一道二维费用的背包模型。
dp[i,j,k]:用前i种硬币，用j个硬币，构成总面额k的最大方案数
dp[i,j,k]=
if(k<num[i]) dp[i-1,j,k]（表示当前总面额k无法用面额为num[i]的硬币组成，因为k比num[i]小）
else dp[i-1,j,k]+dp[i,j-1,k-num[i]]（k>=num[i]时，说明可以用第i种硬币，方案数为不使用第i种硬币和使用的方案的和）
代码如下：
#include #include #include #include typedef long long ll;using namespace std;ll dp[1005][1005]; //用了滚动数组，缩小空间复杂度int num[4]={0,1,2,5};int main(){ int T,n,m,i,j,k; ll ans; cin>>T; while(T--) { cin>>n>>m; ans=0; for(i=0;i<=n;i++) for(j=0;j<=m;j++) dp[i][j]=0; dp[0][0]=1; //dp[0][0]要初始为1，表示用0个硬币构成总面额0的方案有一个，就是什么也不用 for(i=1;i<=3;i++) for(j=1;j<=n;j++) for(k=num[i];k<=m;k++) dp[j][k]+=dp[j-1][k-num[i]]; cout< <
转载地址：http://zddci.baihongyu.com/