天天看点

杭电ACM——2566,统计硬币(DP)

这道题似乎还可以用母函数做出来,不过当时懒得思考,就直接用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<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
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<<dp[n][m]<<endl;
	}
	return 0;
}