a710128 2013-07-23 03:01:00
点我顶贴
收藏
删除
#include<stdio.h>
int f[105][105];//剩m个花瓶 第n种花 摆法
int zl[105],res[105],n,m;
void dp(int shen,int zhon)
{
if(shen<=0||zhon>n){f[shen][zhon]=1; return ;}
for(int i=0;i<=zl[zhon]&&shen-i>=0;i++)
{
if(shen-i>res[zhon+1]) continue ;
if(f[shen-i][zhon+1]==0) dp(shen-i,zhon+1); //如果未知
f[shen][zhon]=(f[shen][zhon]+f[shen-i][zhon+1])%1000007;
}
return ;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&zl[i]);
for(int i=n;i>=1;i--) res[i]=res[i+1]+zl[i];
dp(m,1);
printf("%d",f[m][1]);
return 0;
}
感觉这道题很熟悉啊