POJ 2279. Mr. Young’s Picture Permutations (线性DP)

题面

Description

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.

Input

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.

Output

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.

Sample Input

Sample Output

题目大意

有 $N$个学生（身高为 $1$~ $N$ ）排成$k$ 行拍照，从后到前每行分别有$N_{1}, N_{2}, \cdots, N_{k}$ 个学生。现在要求每行学生从左到右的身高和每列学生从后到前的身高必须按降序排列，求排列这些学生站位的方法总数。

题解

分析

首先考虑到每行的人数 $N_{i}$是给定的，且在转移过程中需要维护当前学生的站位状态，又注意到本题的数据范围很小（$N \leq 30$，$k \leq 5$），因此可以将状态表示为 $f(x_1,x_2,x_3,x_4,x_5)$，其中 $x_{i}$ 表示第$i$ 行当前的学生数目。

再注意到安排学生一定是按照 $1$~ $N$的顺序进行的，且当第 $N-1$名学生的站位安排好后，第 $N$ 名学生的站位就随之确定。但第$i$ ($1 \leq i < N$) 名学生的站位确定时，第$i+1$ 名学生要站在哪一行与前$i$ 名学生的站位有关（因为位置没有填满）；同时注意到，显然这种情况不能出现：

1 4
2 3

这是因为在第1行尚未填满时，第2行已被率先填满，故 $4$只能被填在第1行剩下的空位中。这要求我们必须尽可能先填满后面的行，再去填充前面的行；即要求对第 $i$行和第$i+1$ 行，任何状态中一定有$x_{i}>x_{i+1}$。此时，行和列的降序关系皆可以得到满足。

因此设计状态转移方程为 $$ f(x_1,x_2,x_3,x_4,x_5)=f(x_1-1,x_2,x_3,x_4,x_5)+\ [x_1>x_2] \cdot f(x_1,x_2-1,x_3,x_4,x_5)+\ [x_2>x_3] \cdot f(x_1,x_2,x_3-1,x_4,x_5)+\ [x_3>x_4] \cdot f(x_1,x_2,x_3,x_4-1,x_5)+\ [x_4>x_5] \cdot f(x_1,x_2,x_3,x_4,x_5-1) $$ 其中记号 $[]$ 是艾弗森约定。

最终目标为 $f(N_1,N_2,N_3,N_4,N_5)$。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

typedef unsigned int uint;
typedef long long    ll;

int  a[6];
uint dp[31][16][11][9][7];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);

    int k = 0;
    while (cin >> k && k) {
        memset(a, 0, sizeof(a));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= k; i++)
            cin >> a[i];

        dp[1][0][0][0][0] = 1;
        for (int x1 = 1; x1 <= a[1]; x1++) {
            for (int x2 = 0; (a[2] == 0) || (x2 <= a[2]); x2++) {
                for (int x3 = 0; (a[3] == 0) || (x3 <= a[3]); x3++) {
                    for (int x4 = 0; (a[4] == 0) || (x4 <= a[4]); x4++) {
                        for (int x5 = 0; (a[5] == 0) || (x5 <= a[5]); x5++) {
                            dp[x1][x2][x3][x4][x5] += dp[x1 - 1][x2][x3][x4][x5];

                            if (a[2] && x2 > 0 && x1 >= x2) {
                                dp[x1][x2][x3][x4][x5] += dp[x1][x2 - 1][x3][x4][x5];

                                if (a[3] && x3 > 0 && x2 >= x3) {
                                    dp[x1][x2][x3][x4][x5] += dp[x1][x2][x3 - 1][x4][x5];
                                    
                                    if (a[4] && x4 > 0 && x3 >= x4) {
                                        dp[x1][x2][x3][x4][x5] += dp[x1][x2][x3][x4 - 1][x5];
                            
                                        if (a[5] && x5 > 0 && x4 >= x5) {
                                            dp[x1][x2][x3][x4][x5] += dp[x1][x2][x3][x4][x5 - 1];
                                        }
                                    }
                                }
                            }

                            if (a[5] == 0)
                                break;
                        }
                        if (a[4] == 0)
                            break;
                    }
                    if (a[3] == 0)
                        break;
                }
                if (a[2] == 0)
                    break;
            }
        }

        cout << dp[a[1]][a[2]][a[3]][a[4]][a[5]] << endl;
    }

    return 0;
}

Bonus Time

这是lyd大佬当年的代码，我佛了，%%%

var
 f:array[1..30,0..30,0..15,0..10,0..9,0..6]of dword;
 a:array[1..5]of integer;
 i,j,k,l,m,n,o,p:longint;
begin
 repeat
  readln(n);
  if n=0 then break;
  m:=0;
  fillchar(a,sizeof(a),0);
  for i:=1 to n do
   begin
    read(a[i]);
	inc(m,a[i]);
   end;
  for i:=1 to m do
   for j:=0 to a[1] do
    for k:=0 to a[2] do
	 for l:=0 to a[3] do
	  for o:=0 to a[4] do
	   for p:=0 to a[5] do
	    f[i,j,k,l,o,p]:=0;
  f[1,1,0,0,0,0]:=1;
  for i:=1 to m-1 do
   for j:=1 to a[1] do
    for k:=0 to a[2] do
	 for l:=0 to a[3] do
	  for o:=0 to a[4] do
	   for p:=0 to a[5] do
	    begin
		 if j<>a[1] then f[i+1,j+1,k,l,o,p]:=f[i+1,j+1,k,l,o,p]+f[i,j,k,l,o,p];
		 if (k<>a[2])and(k<j) then f[i+1,j,k+1,l,o,p]:=f[i+1,j,k+1,l,o,p]+f[i,j,k,l,o,p];
		 if (l<>a[3])and(l<k) then f[i+1,j,k,l+1,o,p]:=f[i+1,j,k,l+1,o,p]+f[i,j,k,l,o,p];
		 if (o<>a[4])and(o<l) then f[i+1,j,k,l,o+1,p]:=f[i+1,j,k,l,o+1,p]+f[i,j,k,l,o,p];
		 if (p<>a[5])and(p<o) then f[i+1,j,k,l,o,p+1]:=f[i+1,j,k,l,o,p+1]+f[i,j,k,l,o,p];
		end;
  writeln(f[m,a[1],a[2],a[3],a[4],a[5]]);
 until false;
end.