[数据结构与算法]多重集组合数【dp】

原题链接

题面

思路

首先用过题意可以很容易想到一个三重循环的解决方法：

• 代码是：

  #include<bits/stdc++.h> 
  using namespace std;
  const int N = 1e3 + 10;
  int a[N], f[N][N];
  int main()
  {
  	int n, m, M;
  	cin >> n >> m >> M;
  	for (int i = 1; i <= n; i ++ ) cin >> a[i];
  	f[0][0] = 1;
  	for (int i = 1; i <= n; i ++ )
  	{
  		for (int j = 0; j <= m; j ++ )
  		{
  			for (int k = 0; k <= min(j, a[i]); k ++ )
  			{
  				f[i][j] = f[i][j] + f[i - 1][j - k];
  				f[i][j] %= M;
  			}
  		}
  	}
  	cout << f[n][m] << endl;
  	return 0;
  }
  

  意思是对于第i种物品，选j件时的方案数，可以由不选这件物品时 少用 $k$ 件时的方案数得来

• 定义 $f_{ij}$ 是前 $i$ 种物品选 $j$ 个的方案数

• 当 $j==0$：$f_{ij}=f_{(i?1)j}$

• 当 $1<=j<=k$ ：

  • $f_{ij}=f(i?1)(j?0)+f(i?1)(j?1)+\dots +f(i?1)(j?j)$

  • $f_{i(j?1)}=f(i?1)(j?1)+f(i?1)(j?2)+\dots +f(i?1)(j?j)$

  • 移项得

    $f_{ij}=f_{(i?1)j}+f_{i(j?1)}$

• 当 $k<j$ ：(这里一位是多减了一个，但又因为是大于，所以顶多减成0，不会越界)

  • $f_{ij}=f_{(i?1)(j?0)}+f_{(i?1)(j?1)}+\dots +f_{(i?1)(j?k)}$

  • $f_{i(j?1)}=f_{(i?1)(j?1)}+f_{(i?1)(j?2)}+\dots +f_{(i?1)(j?k)}+f_{(i?1)(j?k?1)}$

  • 移项得

    $f_{ij}=f_{(i?1)(j)}+f_{(i?1)(j?2)}?f_{(i?1)(j?k?1)}+f_{i(j?1)}$

• 最终得到两重循环的代码

  #include<bits/stdc++.h> 
  using namespace std;
  const int N = 1e3 + 10;
  int a[N], f[N][N];
  int main()
  {
  	int n, m, M;
  	cin >> n >> m >> M;
  	for (int i = 1; i <= n; i ++ ) cin >> a[i];
  	f[0][0] = 1;
  	for (int i = 1; i <= n; i ++ )
  	{
  		for (int j = 0; j <= m; j ++ )
  		{
  			if (j == 0) f[i][j] += f[i - 1][j];
  			else if (1 <= j && j <= a[i]) f[i][j] += (f[i - 1][j] + f[i][j - 1]);
  			else if (j > a[i]) f[i][j] += (f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1 - a[i]]);
  			f[i][j] = (f[i][j] + M) % M;
  		}
  	}
  	cout << f[n][m] << endl;
  	return 0;
  }
  

• 注意点，在运算中包含减法，取模时，需要先加上余数再取模，不然有可能变成负数

• 参考

• 

总结

当时写的时候应该是懂了没错，可是现在补题解的时候却又觉得有些一知半解，需要多多复习。