例一:摆花
题目描述
小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共mmm盆。通过调查顾客的喜好,小明列出了顾客最喜欢的nnn种花,从111到nnn标号。为了在门口展出更多种花,规定第iii种花不能超过aia_iai盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算,一共有多少种不同的摆花方案。
输入格式
第一行包含两个正整数nnn和mmm,中间用一个空格隔开。
第二行有nnn个整数,每两个整数之间用一个空格隔开,依次表示a1,a2,…,ana_1,a_2,…,a_na1,a2,…,an。
输出格式
一个整数,表示有多少种方案。注意:因为方案数可能很多,请输出方案数对100000710000071000007取模的结果。
输入输出样例
输入 #12 4 3 2输出 #1
2
方案一:记忆化搜索
#include<bits/stdc++.h> using namespace std; const int maxn=105, mod = 1000007; int n, m, a[maxn], rmb[maxn][maxn]; int dfs(int x,int k) { if(k > m) return 0; if(k == m) return 1; if(x == n+1) return 0; if(rmb[x][k]) return rmb[x][k]; //搜过了就返回 int ans = 0; for(int i=0; i<=a[x]; i++) ans = (ans + dfs(x+1, k+i))%mod; rmb[x][k] = ans; //记录当前状态的结果 return ans; } int main() { cin>>n>>m; for(int i=1; i<=n; i++) cin>>a[i]; cout<<dfs(1,0)<<endl; return 0; }
方法二:动态规划
#include<bits/stdc++.h> using namespace std; int f[1000][1000],a[1000];//f[i][j]表示前i种花总数为j的分法数量 int main() { int n,m; cin>>n>>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=1;k<=min(j,a[i]);k++) f[i][j]=(f[i][j]+f[i-1][j-k])%1000007; cout<<f[n][m]; return 0; }