[NOIP2012 普及组] 摆花

[NOIP2012 普及组] 摆花

题意

有 \(n\) 个数，每种可以选 \(0 \le x_i \le a_i\) 个，问有多少种方法可以使得 \(\sum_{i=1}^n x_i = m\) 。

Solution

1. 深搜 \(dfs\)

显然可以先暴力深搜。

#include "bits/stdc++.h"
using namespace std;
const int maxn = 110,mod = (int)1e6 + 7;
int a[maxn],n,m;
int dfs(int k,int cnt)
{
	if (cnt > m) return 0;
	if (cnt == m) return 1;
	if (k > n) return 0;
	int ret = 0;
	for (int i = 0;i <= a[k];i++)
		ret = (ret + dfs(k+1,cnt+i)) % mod;
	return ret;
}

int main()
{
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
		cin >> a[i];
	cout << dfs(1,0);
	return 0;
}

显然会得到一个大大的 \(\Huge TLE\),但是有30pts呀

2. 深搜优化

众所周知，深搜可以用记忆化搜索来优化, \(f_{i,j}\) 可以表示选到第 \(i\) 个数，已经选了 \(j\) 个数有多少种方案。

#include "bits/stdc++.h"

using namespace std;

const int maxn = 110,mod = (int)1e6 + 7;

int a[maxn],n,m,f[maxn][maxn];


int dfs(int k,int cnt)
{
	if (cnt > m) return 0;
	if (cnt == m) return 1;
	if (k > n) return 0;
	if (f[k][cnt]) return f[k][cnt];
	int ret = 0;
	for (int i = 0;i <= a[k];i++)
		ret = (ret + dfs(k+1,cnt+i)) % mod;
	return f[k][cnt] = ret;
}

int main()
{
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(0);
	
	cin >> n >> m;
	for (int i = 1;i <= n;i++)
		cin >> a[i];
	cout << dfs(1,0);
	return 0;
}

一个浅浅的记忆化搜索，就可以过这道题了，毕竟 \(n,m \le 100\) 。

3.DP

一般来说，可以用记忆化搜索AC的题，也可以用DP做。
\(dp_{i,j}\) 表示用了前 \(i\) 个数，共选了 \(j\) 个数的方案数。
那么状态转移方程就是 $f_{i,j} = \sum_{k = 0}^{min(a_i,\space j)} f_{i-1,j - k} $ 。

#include "bits/stdc++.h"

using namespace std;

const int maxn = 110,mod = (int)1e6 + 7;

int a[maxn],dp[maxn][maxn];

int main()
{
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	
	int n,m;
	cin >> n >> m;
	
	for (int i = 1;i <= n;i++)
		cin >> a[i];
	
	dp[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++)
				dp[i][j] = ( dp[i][j] + dp[i-1][j-k] ) % mod;
	cout << dp[n][m];
	
	return 0;
}

时间复杂度 \(O(nma_i)\) ,显然能过。