RunId : 2856508 Language : G++ Author : huwenbiao
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta
/***************************************************************\
*Author:Hu Wenbiao
*Created Time: Sun 22 Aug 2010 09:47:05 AM CST
*File Name: main.cpp
*Description:组合问题。母函数,其实已经没有了母函数的样子,倒像是一个递推
\***************************************************************/
//*========================*Head File*========================*\\
#include
#include
#include
#include
int m,n,A[12],B[12],C[12];
//*=======================*Main Program*=======================*//
using namespace std;
int main(){
//freopen("input","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF){
for(int i&#61;1;i<&#61;n;i&#43;&#43;){
scanf("%d",A&#43;i);//物品个数
}
memset(B,0,sizeof(B));
memset(C,0,sizeof(C));
for(int i&#61;1;i<&#61;n;i&#43;&#43;){//第i件物品
for(int j&#61;0;j<&#61;m;j&#43;&#43;){//总个数,指数
if(j!&#61;0&&B[j]&#61;&#61;0)//当B[j]是0时&#xff0c;表示没这种排列&#xff0c;于是便不能
//在此基础上再往下构建新排列了&#xff0c;当然j&#61;&#61;0时是初始状态&#xff0c;应当放行。
continue;
for(int k&#61;1;k<&#61;A[i]&&j&#43;k<&#61;m;k&#43;&#43;){//添加的物品个数&#xff0c;(也可以从0开始&#xff0c;下面是赋值)
int method&#61;1;//能构建的排列数
for(int s&#61;1;s<&#61;k;s&#43;&#43;){
method*&#61;(j&#43;s);
method/&#61;s;
}
if(j)
C[j&#43;k]&#43;&#61;method*B[j];//每一种能构建method种&#xff0c;共有method*B[j]
else//j&#61;&#61;0时是特例
C[j&#43;k]&#43;&#61;method;
}
}
for(int j&#61;0;j<&#61;m;j&#43;&#43;){
B[j]&#43;&#61;C[j];//此处不是赋值&#xff0c;要加上去(如果上面从0开始&#xff0c;这里就是赋值&#xff09;
C[j]&#61;0;
}
}
printf("%d\n",B[m]);
}
}