首页 > 分享 > 动态规划摆花题解

动态规划摆花题解

花匠小妙招
2024-11-11 21:04

刚刚卡出了这道动态规划题，特此来发一笔题解啦~

题目内容如下

1123: NOIP2012普及组第3题摆花时间限制: 1 Sec 内存限制: 128 MB
提交: 16 解决: 10
[提交] [状态] [讨论版] [命题人:外部导入] 题目描述

小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。通过调查顾客的喜好,小明列出了顾客最喜欢的n种花,从1到n标号。为了在门口展出更多种花,规定第i种花不能超过ai盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。试编程计算,一共有多少种不同的摆花方案。

【输入输出样例说明】
有2种摆花的方案,分别是(1,1,1,2),(1,1,2,2)。括号里的1和2表示两种花,比如第一个方案是前三个位置摆第一种花,第四个位置摆第二种花。

输入

输入文件共2行。第一行包含两个正整数n和m,中间用一个空格隔开。第二行有n个整数,每两个整数之间用一个空格隔开,依次表示a1、a2、……an。

【数据范围】
对于20%数据，有0<n≤8，0<m≤8，0≤ai≤8；
对于50%数据，有0<n≤20，0<m≤20，0≤ai≤20；
对于100%数据，有0<n≤100，0<m≤100，0≤ ai≤100。

输出

输出只有一行,一个整数,表示有多少种方案。注意:因为方案数可能很多,请输出方案数对1000007取模的结果。

样例输入

2 4 3 2 样例输出

2 来源/分类

说实话在刚刚看到这道题的时候，我的表情是完全僵硬的

那么这一道题到底咋整！？

这一道题看到对1000007取模，就已经能够明显地看出来这道题的正解是动态规划

爆搜根本不行

我们先来整理一下题意完全理解题目的含义是做题的第一步

本题说开了一个花店

要在门口摆一些花Flower~

一共有n种不同的花总共m盆花第 i 种花最多能摆ai盆

题目是看明白了很明显题意已经摆在我们的面前

我本人其实dp也刚入门先来谈一下我个人的非官方想法吧^_^

首先你在dp种肯定要用到ai 这个东西

那么你的 f 数组肯定有一维是跟这个 i 是要挂钩的

i <= n

也就是说你的 f 数组要有一维是 i 表示花的种类

凭直觉（O(∩_∩)O哈哈~）题目中有n和m

n的那一维有了

还要和m挂一点钩鸭

那就再加一维 j 表示花的数量

写到这里其实也只都是一些笼统的通俗的概述

我们来正八经讲一下接下来该怎么办吧

f [ i ] [ j ] 到底表示什么呢

我的想法是前 i 种花摆 j 盆的总方案数

这个其实还是比较好理解的

为甚么非要前 i 种？这样子因为题目问的是总方案数你肯定要从摆前1种前2种前3种一直扩展推推推推推最好到前n种答案就出来啦

摆j盆就和刚才“凭直觉”的解释一致啦就不多做解释了

那么状态转移方程该咋写？？

这困扰了我好久

我们先来写写看

在摆第前 i 种花的时候，你肯定是从前 i-1种花的f数组的值推过来的对吧

那j怎么推的？这个就不能直接简单地转移了

想想看假如摆前i-1种花的时候你一共摆了x盆花

那么现在你肯定是摆x +1 x+2 x+3.。。。盆

那么我们只需要在转移的时候再添加一层循环枚举多添加的盆数就行了

那么当前这种花你最多也就放 j 盆或者a[i]盆

我们把j 和 a[i] 取一个更小的来作为第三层循环的范围

还是粘一段代码稍微看看吧

三层循环搞定

当然你还要来点预处理才能跑起来啊

也很好理解只放前1种花的时候无论摆几盆都只有一种方案

然后放前i种但如果只放0盆那方案当然也只有一种‘

这些预处理都是在dp的过程中进行扩展是要用到的可以手动模拟一波试试看

所以代码完整如下

#include<bits/stdc++.h> using namespace std; int a[105]; int f[105][105]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d",&a[i]); //f[i][j]表示前i种花摆j盆花的总方案数 for(int i=1;i<=a[1];i++) f[1][i]=1; for(int i=1;i<=n;i++) f[i][0]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<=min(j,a[i]);k++) f[i][j]=(f[i][j]+f[i-1][j-k])%1000007; cout<<f[n][m]; return 0; }

加油我们一起进步

看完这篇呕心沥血写完的文章

点个赞再走吧