题意:有\(n\)位同学现在想把他们分成\(k\)横排,每横排的人数为\(a_1,a_2,\cdots,a_k\),分配时应该遵循的规则是,每一横排的同学身高应该从左到右是递减的,每一竖排的同学身高应该前到后递减的,问一共有几种的分配方法,\(\sum_{i=1}^{i=k}a_i \le 30,k \le 5\)。
思路:
同学的身高不需要具体知道,直接用\(1-n\)表示身高从小到大即可
用一个多维的状态来表示排第\(i\)名学生时,\(k\)排已经排好的\(i-1\)名学生对应的状态,考虑对于第\(x\)排在这种状态下满足何种条件可以在放置一个新同学。
\(1.\)当前状态下的\(a_x <= a_i\),即不能超过人数上限。
\(2.\)当前第\(x\)排的人数应当小于\(x-1\)排的人数,否则后面放置的身高一定更高,就没有合法的放置方案了。
#include <bits/stdc++.h> using namespace std; #define pb push_back #define eb emplace_back #define MP make_pair #define pii pair<int,int> #define pll pair<ll,ll> #define lson rt<<1 #define rson rt<<1|1 #define CLOSE std::ios::sync_with_stdio(false) #define sz(x) (int)(x).size() typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-6; const int N = 35; int n,a[N]; ll f[N][N][N][N][N]; void solve() { int sum = 0; for(int i = 1;i <= n;i ++) { scanf("%d",&a[i]); sum += a[i]; } f[0][0][0][0][0] = 1; for(int i = 0;i <= a[1];i ++) { for(int j = 0;j <= a[2];j ++) { for(int k = 0;k <= a[3];k ++) { for(int t = 0;t <= a[4];t ++) { for(int w = 0;w <= a[5];w ++) { if(i) { f[i][j][k][t][w] += f[i-1][j][k][t][w]; } if(j && j <= i) { f[i][j][k][t][w] += f[i][j-1][k][t][w]; } if(k && k <= j) { f[i][j][k][t][w] += f[i][j][k-1][t][w]; } if(t && t <= k) { f[i][j][k][t][w] += f[i][j][k][t-1][w]; } if(w && w <= t) { f[i][j][k][t][w] += f[i][j][k][t][w-1]; } } } } } } printf("%lld\n",f[a[1]][a[2]][a[3]][a[4]][a[5]]); // memset(f,0,sizeof(f)); for(int i = 0;i <= a[1];i ++) { for(int j = 0;j <= a[2];j ++) { for(int k = 0;k <= a[3];k ++) { for(int t = 0;t <= a[4];t ++) { for(int w = 0;w <= a[5];w ++) { f[i][j][k][t][w] = 0; } } } } } for(int i = 1;i <= n;i ++) a[i] = 0; } int main() { while(~scanf("%d",&n)) { if(n == 0) break; solve(); } return 0; }