【dp】P1077摆花

基础DP题

题目描述

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

试编程计算&＃xff0c;一共有多少种不同的摆花方案。

注意&＃xff1a;因为方案数可能很多&＃xff0c;请输出方案数对1000007取模的结果。

对于100%数据&＃xff0c;有0

 

 

我的状态是表示前i盆花中放置j朵的方案数&＃xff0c;所以。

那么就不难得到      且   。其中pre是a的前缀和。

&＃xff08;不过我也很好奇的是为什么j要取0&＃xff0c;按理说f[i,0](i>1)&＃61;0啊&＃xff1f;也去和ARZhu聊了聊&＃xff0c;没有搞出来个直观意义&＃xff09;

&＃xff08;有dalao肯评论一下吗&＃xff01;&＃xff09;