【题目来源】https://www.luogu.com.cn/problem/P1077https://www.acwing.com/problem/content/453/【题目描述】小明的花店新开张为了吸引顾客他想在花店的门口摆上一排花共 m 盆。通过调查顾客的喜好小明列出了顾客最喜欢的 n 种花从 1 到 n 标号。为了在门口展出更多种花规定第 i 种花不能超过 ai 盆摆花时同一种花放在一起且不同种类的花需按标号的从小到大的顺序依次摆列。试编程计算一共有多少种不同的摆花方案。【输入格式】第一行包含两个正整数 n 和 m中间用一个空格隔开。第二行有 n 个整数每两个整数之间用一个空格隔开依次表示 a1a2⋯an。【输出格式】一个整数表示有多少种方案。注意因为方案数可能很多请输出方案数对 10^67 取模的结果。【输入样例】2 43 2【输出样例】2【数据范围】对于 20% 数据有 0n≤80m≤80≤ai≤8。对于 50% 数据有 0n≤200m≤200≤ai≤20。对于 100% 数据有 0n≤1000m≤1000≤ai≤100。【算法分析】● 题意简析一共有 n 种花要摆总共 m 盆花。第 i 种花最多摆 ai 盆。同一种花放一起花种类必须按 1~n 的顺序摆放。求总方案数答案对 10^67 取模。● 设dp[i][j] 表示前 i 种花一共摆 j 盆的方案数。则状态转移方程为其中k 代表第 i 种花摆放 k 盆。且边界条件为 dp[0][0]1即 0 种花摆 0 盆有 1 种方案什么都不放。【算法代码一二维数组】#include bits/stdc.h using namespace std; const int MOD1e67; const int N1e25; int dp[N][N]; int a[N]; int main() { int n,m; cinnm; for(int i1; in; i) { cina[i]; } dp[0][0]1; for(int i1; in; i) { for(int j0; jm; j) { for(int k0; ka[i] kj; k) { dp[i][j](dp[i][j]dp[i-1][j-k])%MOD; } } } coutdp[n][m]endl; return 0; } /* in: 2 4 3 2 out: 2 */【算法代码二一维数组优化】本质是多重背包的一维数组优化问题。k0 代表第 i 种花一盆都不选。这个情况已经提前存进 dp 里了不需要再在循环里再加一遍。所以循环中 k 从 1 开始。#include bits/stdc.h using namespace std; const int MOD1e67; const int N1e25; int dp[N],old[N]; int a[N]; int main() { int n,m; cinnm; for(int i1; in; i) { cina[i]; } dp[0]1; for(int i1; in; i) { for(int t0; tm; t) { old[t]dp[t]; } for(int j0; jm; j) { for(int k1; ka[i] kj; k) { dp[j](dp[j]old[j-k])%MOD; } } } coutdp[m]endl; return 0; } /* in: 2 4 3 2 out: 2 */【参考文献】https://www.luogu.com.cn/problem/solution/P1077https://www.acwing.com/solution/content/4902/