蓝桥杯算法提高VIP

题目

题目链接

题解

动态规划。

题目大意：总共n种花，每种花ai株，总共m个盆，花放在盆里的方案数，要求种号小的花必须在种号大的花前面，且同种花不分彼此（不存在内部排序）。

dp[i][j]表示i种花，j个盆的方案数，同时也要满足数量的要求。
转移方程：

注意j：0~m；i：1~n。

对于前i种花，我可以选择放0株第i种花，那么剩下的j个盆要放前i-1种花；我也可以选择放1株第i种花，剩下的j-1个盆放前i-1种花；……；我还可以选择放ai株第i种花，剩下的0个盆放前i-1种花。这些方案数累加起来就是前i种花放在j个盆中的方案数。

代码

#include<bits/stdc++.h> using namespace std; const int MOD = 1000007, N = 110; int dp[N][N], a[N], n, m; int main() {cin>>n>>m;for(int i = 1;i <= n;i ++) cin>>a[i];memset(dp, 0, sizeof dp);dp[0][0] = 1;for(int i = 1;i <= n;i ++)for(int j = 0;j <= m;j ++)for(int k = 0;k <= a[i] && k<=j;k ++)dp[i][j] = ( dp[i][j] + dp[i-1][j-k] ) % MOD;cout << dp[n][m] << endl;return 0; }

相关知识

蓝桥杯算法提高VIP
蓝桥杯样题
C#：实现模拟花卉进化过程算法（带源代码）
中国农科院蔬菜花卉所开发异交物种基因高效定位的新算法工具OcBSA
6/13每周一更新：APP新增“VIP推送订购”渠道+接单区域设置！
第五届中国杯插花花艺比赛广州落幕
“索尼杯”婚庆视频大赛颁奖典礼隆重举行
春风十里，正植有你—DIY滴胶干花杯垫
第三届中国杯插花花艺大赛在常州举办
第三届“中国杯”插花花艺大赛在常精彩开幕

网址: 蓝桥杯算法提高VIP https://www.huajiangbk.com/newsview44351.html