[Acwing] 281. 硬币 背包问题

前言

传送门 :

题意

给你 n n n个数,每个数 c c c次选法,询问有多少数可以被凑出来

一看以为是 多重背包方案数问题 ,结果一看数据范围感觉会T

思路

首先 如果使用多重背包的思路 d p [ i ] [ j ] dp[i][j] dp[i][j]前 i i i个物品整合出 j j j的方案

如果前 i − 1 i-1 i−1个物品已经 d p [ i − 1 ] [ j ] = 1 dp[i-1][j]=1 dp[i−1][j]=1 显然 d p [ i ] [ j ] = 1 dp[i][j] = 1 dp[i][j]=1

如果前 d p [ i ] [ j − a [ i ] ] = 1 dp[i][j-a[i]]=1 dp[i][j−a[i]]=1,那么 d p [ i ] [ j ] = 1 dp[i][j] = 1 dp[i][j]=1 因此贪心的来说,我们可以去掉 多重

背包枚举的那一层。

因此不妨设 f [ i ] [ j ] f[i][j] f[i][j]表示前 i i i个物品,整合出 j j j时还剩的最大次数

考虑状态转移 f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j] = f[i-1][j] f[i][j]=f[i−1][j] f [ i ] [ j ] = f [ i ] [ j − a [ i ] ] − 1 f[i][j] = f[i][j-a[i]]-1 f[i][j]=f[i][j−a[i]]−1

Mycode

int a[N],c[N],dp[N][M];

/**
前i种硬币种 组成恰好为j时 第i种硬币最多剩余多少个
**/
void solve()
{
	for(int i=1;i>a[i];
	for(int i=1;i>c[i];
	
	memset(dp,-1,sizeof dp);
	dp[0][0] = 1;
	
	for(int i=1;i=0 && dp[i][j-a[i]] >= 1){
					dp[i][j]= dp[i][j-a[i]] - 1;
				}
			}
		}
	}
	
	int ans =  0 ;
	for(int j=1;j=0 ) ++ans;
	}
	
	cout