状态设计:
$$ f[t_1][t_2][t_3][t_4][t_5]代表每行已经站了t_i个学生时的方案数$$
每次枚举每个学生放在第几行即可
为了满足单调性,每行的学生数必须是递增的
--------不怎么华丽的分割线--------
yxc大佬写的是五层循环判断,但是我懒,所以:
记忆化搜索!
上面记忆化的同学是用abcde作为状态,我直接把状态存到了数组里,这样连五层判断也省了
有一个细节就是对于每个状态t,它的f是唯一确定的,与输入无关,这样还省了初始化的时间(受到上面同学的启发)
写出来只有25行,时间24ms,又加了一个define,看起来比较简洁
#include<bits/stdc++.h>
#define N 32
#define now f[t[1]][t[2]][t[3]][t[4]][t[5]]
using namespace std;
int n,x[7];
long long f[N][N][N][N][N];//每排已填写的人数
long long F(int t[]){
if(now) return now;
long long &res=now;
for(int i=1;i<=n;++i)if(t[i]&&t[i]>t[i+1]){
--t[i];
res+=F(t);
++t[i];
}
return now;
}
int main(){
f[0][0][0][0][0]=1;
while(cin>>n&&n){
memset(x,0,sizeof(x));
for(int i=1;i<=n;++i)scanf("%d",&x[i]);
printf("%lld\n",F(x));
}
return 0;
}
666 %%%