记录编号	460477	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]摆花	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2017-10-17 12:49:25	内存使用	0.35 MiB

#include<cstdio>
#include<iostream>
const int maxn=1000007;
using namespace std;
inline int get();
void dfs(int a,int b);
int n,m;
int sum[101],alone[101],f[101][101];
int main()
{
	freopen("flower.in","r",stdin);
	freopen("flower.out","w",stdout);
	n=get(),m=get();
	for(int i=1;i<=n;i++)alone[i]=get(),sum[i]=sum[i-1]+alone[i];
	dfs(m,n);
	printf("%d\n",f[m][n]);
	return 0;
}
void dfs(int a,int b)
{
	if(f[a][b])return;
	if(sum[b]==a||b==1)
	{
		f[a][b]=1;
		return;
	}
	for(int i=max(0,a-sum[b-1]);i<=alone[b]&&i<=a;i++)
	{
		dfs(a-i,b-1);
		f[a][b]=(f[a][b]+f[a-i][b-1])%maxn;
	}
}
inline int get()
{
	int t=0;char c=getchar(),j=1;
	while(!isdigit(c))
		if(c=='-')j=-1,c=getchar();
		else c=getchar();
	while(isdigit(c))
		t=(t<<3)+(t<<1)+c-'0',
		c=getchar();
	return j*t;
}