[CF543A]/[CF544C]Writing Code

题目大意：

有\(n\)种物品，每种物品分别要\(c_i\)的代价，每个物品有\(1\)的体积，每个物品可以选多个，代价不能超过\(b\)，求正好填满大小为\(m\)的背包的方案数。

思路：

\(f[i][j]\)表示有\(i\)个物品，总代价为\(j\)的方案数。\(\mathcal O(n^3)\)DP即可。

源代码：

#include<cstdio>

#include<cctype>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=501,mod=1e9+7;

int f[N][N];

int main() {

	const int n=getint(),m=getint(),b=getint();

	f[0][0]=1;

	for(register int i=1;i<=n;i++) {

		const int x=getint();

		for(register int j=1;j<=m;j++) {

			for(register int k=x;k<=b;k++) {

				(f[j][k]+=f[j-1][k-x])%=mod;

			}

		}

	}

	int ans=0;

	for(register int i=0;i<=b;i++) {

		(ans+=f[m][i])%=mod;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

[CF543A]/[CF544C]Writing Code

[CF543A]/[CF544C]Writing Code

题目大意：

思路：

源代码：

最新文章

热门文章