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;

	}