找钱 [多重背包计数]

(mathcal{Description})
小 (L) 所在的 (L) 国由于没有普及移动支付,依然在大规模使用纸币。一共有 (n)
种面值的纸币,面值互不相同。一天小 (L) 去商店购买一个价格为 (X) 元的物品,
他提前知道了自己手里和店员手里每种面值的纸币的数量,他想知道一共有多少
种付钱-找钱的方式。两种付钱-找钱的方式不同,当且仅当存在一种面值,在两
种方案中小 (L) 付出的该种面值的纸币数量不同或店员找的该种面值的纸币数量
不同。此外,设小 (L) 付出的纸币面值总数为 (Y),则小 (L) 付出的纸币中不能存在
面值小于等于 (Y-X) 的纸币(不然就没有必要付这张纸币了)。

输入格式
第一行输入两个正整数 (n,X),分别表示纸币面值的数量以及小 L 想要购买的商品的价格。
接下来 (n) 行每行三个整数 (a_i,b_i,c_i),分别表示第 i 种纸币的面值,小 X 拥有的该种纸币数量,店员拥有的该种纸币数量,保证面值 (a_i) 单调增加。

输出格式
一行输出一个整数,表示总方案数对 (1000000007) 取模的结果。

数据范围
对于所有数据,满足 (ai>0);
对于 (30\%)的数据,(n,X,ai,bi,ci≤8);
对于 (60\%)的数据,(n,X,ai,bi,ci≤100);
对于 (100\%)的数据,(n≤1000,X,ai,bi,ci≤10000)。

(mathcal{Solution})
两种方法

显然的想法是做多重背包
设(fa_i)表示小(L)能够符合题意地凑出(i)元的方案数
(fb_i)表示店员能够找出(i)元的方案数
便可以直接多重背包
暴力(D)显然会超时,用二进制分组还是会(T)

法一
设枚举到的钱币面值为(w),数量为(num)
观察发现,(f_i=f_{i-w}+f_{i-2w}+ldots+f_{i-kw}),其中(kleq num)
考虑设(s_i)表示(f_{i}+f_{i-w}+f_{i-2w}+ldots+f_{i-kw}),其中(igeq kw,i< (k+1)w)
于是有(f_i=s_i-[igeq (num+1)w]s_{i-(num+1)w})
对于每个物品都这么做,复杂度为(nX)

法二
这个方法好像是套路,对于多重背包计数就可以这样做
类似于容斥
仍然是设枚举到的钱币面值为(w),数量为(num)
先不管上界直接做完全背包
之后将算多了的减去
即(f_i-=f_{i-(num+1)w})

实际上,这两种方法是换汤不换药的

(mathcal{Code})

/*******************************
Author:Morning_Glory
LANG:C++
Created Time:2019年10月21日 星期一 20时18分58秒
*******************************/
#include <cstdio>
#include <fstream>
using namespace std;
const int maxn = 20004;
const int mod = 1000000007;
//{{{cin
struct IO{
	template<typename T>
	IO & operator>>(T&res){
		res=0;
		bool flag=false;
		char ch;
		while((ch=getchar())>'9'||ch<'0')	flag|=ch=='-';
		while(ch>='0'&&ch<='9')	res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
		if (flag)	res=~res+1;
		return *this;
	}
}cin;
//}}}
int n,c,ans;
int fa[maxn],fb[maxn],w[maxn],ha[maxn],hb[maxn],s[maxn];
//{{{M 就是优化取模过程
int M (long long x)
{
	if (x<0){
		if (x+mod>0)	return x+mod;
		return x%mod+mod;
	}
	if (x<mod)	return x;
	if (x-mod<mod)	return x-mod;
	return x%mod;
}
//}}}
//{{{solve
void solve (int *f,int v,int num)
{
	for (int i=0;i<v;++i)	s[i]=f[i];
	int up=c+v-1;
	for (int i=v;i<=up;++i){
		s[i]=M(s[i-v]+f[i]);
		f[i]=s[i];
		if (i>=(num+1)*v)	f[i]=M(f[i]-s[i-(num+1)*v]);
	}
}
//}}}
int main()
{
	cin>>n>>c;
	for (int i=1;i<=n;++i)	cin>>w[i]>>ha[i]>>hb[i];
	fa[0]=fb[0]=1;
	
	for (int i=n;i>=1;--i)	solve(fa,w[i],ha[i]),solve(fb,w[i],hb[i]);
	for (int i=w[n]+c;i>=c;--i)	ans=M(ans+M(1ll*fa[i]*fb[i-c]));

	printf("%d
",ans);
	return 0;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧

找钱 [多重背包 计数]

找钱 [多重背包计数]