AcWing 271. Teacher Yang's photographic arrangement [multidimensional DP]

 271. Mr. Yang's photo arrangement - AcWing Question bank

The question ：

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

Ideas ：

  The essence of ：

• Simulation operation , Only simulation can operate , Just know that for the current step , Which steps should be updated , You can specialize your “ Each step ”,f It can also be specialized , Because after you find specialization , After finding some features that represent , Reduced the original state space , But the space represented by the answer is still in your specialized state space , In this way, the problem can be specialized , Try and make mistakes through bold speculation and practice , Grasp the essence of the problem .
• aggregate ： This set is defined by the property of quantity . Why? ？ Because during the simulation, it is found that the current number must be placed on the leftmost side of the same line , And there must be no space above .

First ,1 It must be placed in the upper left corner first , Others cannot undertake this important task . And then 2 Must be in these two positions , Other positions either have spaces on the left , Or there is a space above , Not in accordance with the regulations . therefore , We found that when we put the number , Not even as concerned as the longest ascending subsequence tail Value , Because the title itself has “ monotonicity ”, In other words, you just need to simulate according to the meaning of the topic .

What we care about is ： When you want to put the current number , It's time to gather “ shape ”, That is, the number of each line

•   The title gives special k The scope of the ,k The maximum is five floors , Special small scope and multi dimension dp relevant
• initialization 、 The order problem of cyclic topology update .

f[0][0][0][0][0] = 1;

For this question , Take any one dimension 0, Take any dimension 0, There are many situations in which one dimension is taken or not taken, which is very troublesome to consider , And these f Have practical significance , Corresponding to the actual situation , This question is from all to 0 Updated step by step , So initialization is only used. Initialization is all 0 Of f that will do . For this, we should start from 0 The beginning is basically 0 Initialize to 1, Others do not need to be initialized .

Since from 0 At the beginning, the following topological order must also be equal .

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 31;
ll f[N][N][N][N][N];
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 	int n;
 	while(cin >> n, n) {
 		int s[5] = {0};
 		for (int i = 0; i < n; i ++ ) cin >> s[i];
 		memset(f, 0, sizeof f);
 		f[0][0][0][0][0] = 1;
 		//
 		for (int a = 0; a <= s[0]; a ++ ) {
 			for (int b = 0; b <= min(s[1], a); b ++ ) {
 				for (int c = 0; c <= min(s[2], b); c ++ ) {
 					for (int d = 0; d <= min(s[3], c); d ++ ) {
 						for (int e = 0; e <= min(s[4], d); e ++ ) {
 							ll &x = f[a][b][c][d][e];
 							if(a && a - 1 >= b) x += f[a - 1][b][c][d][e];
 							if(b && b - 1 >= c) x += f[a][b - 1][c][d][e];
 							if(c && c - 1 >= d) x += f[a][b][c - 1][d][e];
 							if(d && d - 1 >= e) x += f[a][b][c][d - 1][e];
 							if(e) x += f[a][b][c][d][e - 1];
 						}
 					}
 				}
 			} 
 		}
 		cout << f[s[0]][s[1]][s[2]][s[3]][s[4]] << '\n';
 	}    
	return 0;
}