Acwing271 [teacher Yang's photographic arrangement] [linear DP]

Yes N A group photo of two students , Stand with the left end aligned k row , Each row has N1,N2,…,Nk personal . (N1≥N2≥…≥Nk)

The first 1 Line up at the back , The first k Line up at the front .

The students are different in height , Mark them from top to bottom as 1,2,…,N.

When taking group photos, the height of each row shall decrease from left to right , The height of each column decreases from the back to the front .

How many plans are there to arrange the location of the group photo ？

The following row of triangular matrices gives when N=6,k=3,N1=3,N2=2,N3=1 All of time 16 A group photo scheme . Note that the tallest person is 1, The lowest is 6.

123 123 124 124 125 125 126 126 134 134 135 135 136 136 145 146
45 46 35 36 34 36 34 35 25 26 24 26 24 25 26 25
6 5 6 5 6 4 5 4 6 5 6 4 5 4 3 3
Input format
Input contains multiple sets of test data .

Two lines of data for each group , The first line contains an integer k Indicates the total number of rows .

The second line contains k It's an integer , Indicates the specific number of people in each row from the back to the front .

When the input k=0 When the data is , Indicates that the input is terminated , And the data does not need to be processed .

Output format
Output one answer for each set of test data , Indicates the number of different arrangements .

Each answer takes up one line .

Data range
1≤k≤5, The total number of students does not exceed 30 people .

sample input ：
1
30
5
1 1 1 1 1
3
3 2 1
4
5 3 3 1
5
6 5 4 3 2
2
15 15
0
sample output ：
1
1
16
4158
141892608
9694845

Ideas ： We consider the position of each student from high to low , Stand in line according to a certain principle , In this order, we can ensure that the height of students in each row and column is monotonically decreasing
This principle satisfies two conditions ：
1. The station is not full yet
2. The number of people standing in the last row or row of the standing row is less than that in the back row .
Suppose it is now someone's turn ( The first a+b+c+d+e individual ) Students enter the team , He chose the first row ,5 The number of platoons used to be f[a-1,b,c,d,e] people ,a-1,b,c,d,e Are greater than or equal to zero Then there are f[a,b,c,d,e] += f[a-1,b,c,d,e], If the second row is selected and the above two conditions are met , There is f[a,b,c,d,e]+=f[a,b-1,c,d,e];

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 31;
typedef long long ll;
ll f[N][N][N][N][N];
int main(){
    
    int n;
    while(~scanf("%d",&n),n){
    
        memset(f,0,sizeof(f));
        int s[5]={
    0};
        for(int i=0;i<n;i++) scanf("%d",&s[i]);
        f[0][0][0][0][0]=1;
        for(int a=0;a<=s[0];a++)
            for(int b=0;b<=min(a,s[1]);b++)
                for(int c=0;c<=min(b,s[2]);c++)
                    for(int d=0;d<=min(c,s[3]);d++)
                        for(int e=0;e<=min(e,s[4]);e++){
    
                            ll &temp=f[a][b][c][d][e];
                            if(a&&a-1>=b) temp+=f[a-1][b][c][d][e];
                            if(b&&b-1>=c) temp+=f[a][b-1][c][d][e];
                            if(c&&c-1>=d) temp+=f[a][b][c-1][d][e];
                            if(d&&d-1>=e) temp+=f[a][b][c][d-1][e];
                            if(e) temp+=f[a][b][c][d][e-1];
                        }
        printf("%lld\n",f[s[0]][s[1]][s[2]][s[3]][s[4]]);
    }
    
}