P1077 [NOIP2012 普及组] 摆花

题目描述

动态规划求解(01背包)

分析

一共有sum(a[i])个花，每个花看成一个物品，盆的数量看成背包容量，那么本题就是考察容量为m的背包装这些物品，最多有多少种方案
用f[i][j]表示前i种花，有j个盆的时候，最多的方案
那么f[i][j] = sum( f[i-1][j - k]) 0 <= k <= min(a[i], j)，也就是当第i种花分别选0，1，2，...，a[i]个的时候的方案数相加

注意初始化的时候，f[0][0] = 1; // 这个很重要

代码

#include
#include
using namespace std;

const int mod = 1e6 + 7;
const int N = 110;
int n, m; // n是种类数，m是容量 
int a[N], f[N][N]; // f[i][j]表示前i种花 一共摆j盆的时候的最大方案数

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	
	f[0][0] = 1; // 摆0盆花的时候，就只有一个都不选这一种方案 ;一个数都不选的时候和为0，所以方案数为1
	
	for(int i = 1; i <= n; i++) // 前i种花
	{
		for(int j = 0; j <= m; j++) // 一共摆放j盆花 
		{
			for(int k = 0; k <= a[i] && k <= j; k++)
			{
				f[i][j] = (f[i][j] + f[i-1][j - k]) % mod;
			 } 
		}	
	}	
	
	printf("%d\n", f[n][m]);
	return 0;
} 

时间复杂度

\(O(m*n*max(a[i]) = O(n^3)\)

参考文章

https://www.luogu.com.cn/problem/solution/P1077?page=2