线性dp，
每一个ai < ni 并且 i = 1 或者 ai-1 > ai ; 这两个条件都必须满足；
初始化 f 00000 = 1 ,没有人安排的时候是一种情况
转移 如果a1 < n1 , 就让f[a1 + 1, a2 ,a3 ,a4, a5] += f[a1,a2,a3,a4,a5] ;
如果a2 < n2 并且 a1 > a2 ,则令f[a1 , a2+1 ,a3 , a4,a5] += f[a1,a2,a3,a4,a5] ;
以此类推
#include<iostream> #include<cstring> #include<algorithm> using namespace std ; typedef long long LL ; const int N = 35 ; LL f[N][N][N][N][N] ;// 一个五维数组，表示第i排已经安排了n个人； int n ; int m[6] ;//记录每一排的最多数量 int main(){ while(cin >> n , n){ memset(m,0,sizeof(m)) ; memset(f,0,sizeof(f)) ; for(int i = 1 ; i <= n; i ++) cin >> m[i] ; f[0][0][0][0][0] = 1 ;//初始化 for(int a1 = 0 ; a1 <= m[1] ; a1 ++){ for(int a2 = 0 ; a2 <= m[2] && a2 <= a1 ; a2 ++){ for(int a3 = 0 ; a3 <= m[3] && a3 <= a2; a3 ++){ for(int a4 = 0 ; a4 <= m[4]&& a4 <= a3 ; a4 ++){ for(int a5 = 0 ; a5 <= m[5] && a5 <= a4; a5 ++){ LL &x = f[a1][a2][a3][a4][a5] ; if(x == 0) continue ; if(a1 && a1 < m[1]) f[a1+1][a2][a3][a4][a5] += x ; if(a2 && a2 < m[2] && a1 > a2) f[a1][a2+1][a3][a4][a5] += x ; if(a3 && a3 < m[3] && a2 > a3) f[a1][a2][a3+1][a4][a5] += x ; if(a4 && a4 < m[4] && a3 > a4) f[a1][a2][a3][a4+1][a5] += x ; if(a5 && a5 < m[5] && a4 > a5) f[a1][a2][a3][a4][a5+1] += x ; } } } } } cout << f[m[1]][m[2]][m[3]][m[4]][m[5]] << endl ; } }
