补题计划---摆花（有意思的一道dp）

补题计划，也是我的oi生涯的最后一章，如果这一次能够成功，至少以一个正规选手能参加一次正规的比赛一次，为了自己那几年高中的努力，泪水，确实，该开始了，如果12月的那次校级比赛，没有得到大三的认可，那......这次的oi之旅真的要结束了。我虽然也不想让他翻篇，不想结束那些在机房里一个静静地写题，不被任何人认可的那段寂静。但天下没有不散的宴席，如果没有，那么该翻篇了。最后一次。

时间、运气、命运对 OIer 们来说是残酷的字眼。再强的 OIer，也有退役的时刻。再努力的 OIer，也难以保证他在省选或 NOI 一定能够有和他的付出对等的回报。这是很多 OIer 心知肚明的事实，也是我们无力感的根源。

也正因为此，有的人选择了把OI当成生命中的过客，没有对它付出过多的精力和情感。但另外一些人仍然把OI当作自己的归宿，甚至当成生活的全部。究其原因，是因为他们给OI这个词赋予了太多的意义和价值。

他们坚持停课，坚持与班主任老师、甚至家长“对抗”，坚持自己心中的目标。他们舍弃了睡觉时间来打 CF，舍弃了文化课来刷模拟赛。有时，他们要面对的是孤独、不理解和对自己前途的恐惧。你可以说，这是坚持、执着、勇往直前，但在命运面前，这是渺小、卑微的。一场考试的结果是难以预料的，一个字符之差就可能是 100 分与 0 分之差，一个部分分之差就可能是 20 多名的差距。最勤奋的人，也不敢说，自己能够掌握自己的未来。

摆花

题目描述

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

试编程计算，一共有多少种不同的摆花方案。

输入格式

第一行包含两个正整数 \(n\) 和 \(m\)，中间用一个空格隔开。

第二行有 \(n\) 个整数，每两个整数之间用一个空格隔开，依次表示 \(a_1,a_2, \cdots ,a_n\)。

输出格式

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 \(10^6+7\) 取模的结果。

样例 #1

样例输入 #1

2 4
3 2

样例输出 #1

2

提示

【数据范围】

对于 \(20\%\) 数据，有 \(0<n \le 8,0<m \le 8,0 \le a_i \le 8\)。

对于 \(50\%\) 数据，有 \(0<n \le 20,0<m \le 20,0 \le a_i \le 20\)。

对于 \(100\%\) 数据，有 \(0<n \le 100,0<m \le 100,0 \le a_i \le 100\)。

思路

刚开始我想的是让 \(dp_{i,j,k}\) 表示为摆在第i个位置，摆的第j种花盆的第k个。但是好像细想有点反直觉，就是有点感觉有点不对。最后我想到，其实i可以省略，因为这个摆的花盆与j与k有关（因为题目说花盆有序），就是一个单调不下降子序列。

本来想是通过直接去掉i，但是细想这种又有点不对，最后求最后有多少种的时候又有不知道输出什么。

看了我之前的代码，我理解了，就是可以定义 \(d_{i,j}\) 为在用到第 i 种花时，用了第 \(j\) 盆花的方案数（注意：这里\(j\)指的是全体的\(j\)盆，而不是\(a_{i}\)的第\(j\)盆。

这样对于每个 \(d_{i,j}\) 可以去更新后面的 \(d_{i+1,j+k}\)， k表示对于第 i 种花的约束。

那么动态转移方程为：

\[d_{i+1,j+k} = d_{i+1,j+k} + d_{i,j} \qquad (k = 1,2,....a_i)\]

xxxxxxxxxx31 1#include<bits/stdc++.h>2​3using namespace std;4​5int T;6​7int main()8{9 int T;10 cin>>T;11 while(T--){12 int n,r;13 cin>>n>>r;14 int cnt1 = 0,ans = 0;15 for(int i=1;i<=n;i++){16 int x;cin>>x;17 cnt1 += (x % 2);18 ans += (x/2)2; 19 r -= (x/2);20 }21 22 if(r >= cnt1) ans += cnt1;23 else{24 int t = cnt1 - r;25 ans += (cnt1 - t2);26 }27 28 cout<<ans<<endl;29 }30 return 0;31}cpp

以后遇到好题，都会加入补题计划（如果这次失败了，那也该和OI说再见了，一心一意的开始考研了）。