P1077 摆花

题目描述

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

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

输入输出格式

输入格式:

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

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

输出格式:

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


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

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

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long
using 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;
}
05-08 15:27