Mr. Young wishes to take a picture of his class. The students will stand in rows with each row no longer than the row behind it and the left ends of the rows aligned. For instance, 12 students could be arranged in rows (from back to front) of 5, 3, 3 and 1 students.

X X X X X

X X X

X X X

X

In addition, Mr. Young wants the students in each row arranged so that heights decrease from left to right. Also, student heights should decrease from the back to the front. Thinking about it, Mr. Young sees that for the 12-student example, there are at least two ways to arrange the students (with 1 as the tallest etc.):

1  2  3  4  5     1  5  8 11 12

6  7  8           2  6  9

9 10 11           3  7 10

12                 4

Mr. Young wonders how many different arrangements of the students there might be for a given arrangement of rows. He tries counting by hand starting with rows of 3, 2 and 1 and counts 16 arrangements:

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

Mr. Young sees that counting by hand is not going to be very effective for any reasonable number of students, so he asks you to help out by writing a computer program to determine the number of different arrangements of students for a given set of rows.

输入描述:

The input for each problem instance will consist of two lines. The first line gives the number of rows, k, as a decimal integer. The second line contains the lengths of the rows from back to front (n1, n2,..., nk) as decimal integers separated by a single space. The problem set ends with a line with a row count of 0. There will never be more than 5 rows and the total number of students, N, (sum of the row lengths) will be at most 30.

输出描述:

The output for each problem instance shall be the number of arrangements of the N students into the given rows so that the heights decrease along each row from left to right and along each column from back to front as a decimal integer. (Assume all heights are distinct.) The result of each problem instance should be on a separate line. The input data will be chosen so that the result will always fit in an unsigned 32 bit integer.

输入样例:

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

输出样例:

1
1
16
4158
141892608
9694845

题目分析

首先,要计算安排方案数,那么不可避免的需要将某学生安排到某一位置上,我们考虑这个过程。 能够将某学生安排在某行的前提是:

  • 该行的当前人数满足小于后面一行且小于该行被规定的人数。
  • 这个学生的高度低于将安排位置左边的同学的高度和后一行对应位置的同学的高度。

对于第二个条件, 只要我们严格按照高度从大到小依次选取同学,并按照从后往前从左往右的顺序安排该同学的位置,那么可以将此条件忽律。

我们考虑DP: 对于函数 f(i, j, k, l, m), 我们认为是第 5 行人数为 i , 第 4 行人数为 j, 第 3 行人数为 k, 第 2 行人数为 l , 第 1 行人数为 m 的情况下的总安排方案数。 那么边界条件 f(0,0,0,0,0) = 1 (每行都不安排人,有一种方案)

而状态转移方程是显而易见的: $$ f(i, j, k, l, m) = f(i - 1, j, k, l, m) + f(i, j - 1, k, l, m) + f(i, j, k - 1, l, m) + f(i, j, k, l - 1, m) + f(i, j, k, l, m - 1) $$

代码实现

#include <iostream>
#include <cstring>
using namespace std;
using LL = long long;
const int N = 10, M = 55;

int n, s[N];
LL dp[M][M][M][M][M];
LL solve() {
    memset(s, 0, sizeof s);
    for(int i = 1; i <= n; ++i) cin >> s[i];
    dp[0][0][0][0][0] = 1;
    for(int i = 1; i <= s[1]; ++i) {
        for(int j = 0; j <= min(i, s[2]); ++j) {
            for(int k = 0; k <= min(j, s[3]); ++k) {
                for(int l = 0; l <= min(k, s[4]); ++l) {
                    for(int m = 0; m <= min(l, s[5]); ++m) {
                        auto& cur = dp[i][j][k][l][m];
                        if(i - 1 >= 0) cur = dp[i - 1][j][k][l][m]; 
                        if(j - 1 >= 0) cur += dp[i][j - 1][k][l][m];
                        if(k - 1 >= 0) cur += dp[i][j][k - 1][l][m];
                        if(l - 1 >= 0) cur += dp[i][j][k][l - 1][m];
                        if(m - 1 >= 0) cur += dp[i][j][k][l][m - 1];
                    }
                }
            }
        }
    }
    return dp[s[1]][s[2]][s[3]][s[4]][s[5]];
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(cin >> n, n) cout << solve() << '\n';
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status