P1077 摆花

题目描述

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

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

输入输出格式

输入格式：

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

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

输出格式：

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

---

首先想暴力， 预计30 \(pnts\)

然后发现摆花只能按顺序摆放， 所以此种花选 \(a\) 个是否合法只与后面的花摆放方法是否合法有关。 不难想到，在摆放顺序确定和摆放必须连着则两种限制下， 对于一种花的摆放方案， 当在此时已经摆了的花数是确定了的时候， 其方案数是一定的， 所以考虑记忆化搜索

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long longusing namespace std;int RD(){    int flag = 1, out = 0;char c = getchar();    while(c < '0' || c > '9'){if(c == '-')flag = -1;c = getchar();}    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}    return flag * out;    }const int maxn = 1019, M = 1000007;int num, m;int a[maxn];int dp[maxn][maxn];int DP(int index, int cnt){    if(dp[index][cnt])return dp[index][cnt];    if(index == num + 1){        if(cnt == m)return 1;        else return 0;        }    for(int i = 0;i <= a[index];i++){        if(cnt + i <= m)dp[index][cnt] += DP(index + 1, cnt + i);        dp[index][cnt] %= M;        }    return dp[index][cnt];    }int main(){    num = RD();m = RD();    for(int i = 1;i <= num;i++)a[i] = RD();    LL ans = DP(1, 0) % M;    printf("%lld\n", ans);    return 0;    }