刚刚卡出了这道动态规划题, 特此来发一笔题解啦~
题目内容如下
1123: NOIP2012 普及组第 3 题 摆花
时间限制: 1 Sec 内存限制: 128 MB
提交: 16 解决: 10
[提交 http://qdoj.xyz/submitpage.php?id=1123 ] [状态 http://qdoj.xyz/problemstatus.php?id=1123 ] [讨论版 http://qdoj.xyz/bbs.php?pid=1123 ] [命题人: 外部导入]
题目描述
小明的花店新开张, 为了吸引顾客, 他想在花店的门口摆上一排花, 共 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
来源 / 分类
http://qdoj.xyz/problemset.php?search=NOIP
说实话 在刚刚看到这道题的时候, 我的表情是完全僵硬的
那么这一道题到底咋整!?
这一道题看到对 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;
- }
加油 我们一起进步
看完这篇呕心沥血写完的文章
点个赞再走吧
~
'
来源: https://www.cnblogs.com/Tidoblogs/p/11253379.html