Mr. Young's Picture Permutations
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 5841 | Accepted: 1860 |
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.
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.):
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:
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.
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
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
题目不难，有几个值得学习的地方（就是我不会的地方）
首先是这个思考方式，也就是对这个问题特征的分析
我们要计算所有的方式，计数类题目基本都是这种套路，要么是直接用数学大力分析一手，然后各种组合数乘法原理加法原理
要么就是根据这个题目的特别性进行一个稍微类似枚举的过程
对于这个，直接枚举所以可能性自然是非常的不可行的，连样例都不可能过
我们考虑一个构造的过程，假设我们已经有了一个不完整但是暂时合法的组合，我们考虑给它加上一个数字
可以发现，如果这个是合法的，那么它从左上到右下的数字应该是在逐渐增大的（并不严谨，但是可以先这样理解一下）
那么我们就从左上方开始构造，因为可以发现1永远要在左上角，这个应该是容易证明的
我们就从这个确定的1开始，保证这个方阵合法的情况下，向着左边和下边进行构造
我们试着把所有数字从1开始由小到大逐渐放进这个方阵中，为了保证这个方阵始终合法，我们需要考虑一下应该按照什么样子的规则来进行
首先，每一个数字下面的的数字肯定是要比这个数字大的，而我们在构造的时候是从小到大的，所以只要后放就更大
也就是说，一个数字右边或者是下面的数字肯定是要在这个数字后放的。
也就是说，在一个数字被放下前，它的上面和左边的数字肯定是已经被放好的。
利用这个规则，我们就可以开始dp了
设f[a][b][c][d][e]为当第一排有a个人，第二排有b个人，第三排有c个人·····时的合法方案数
用k[i]表示第i排最多的人数
转移（也许算是递推吧？）的方程就是
对于第一排，当a<k1时，让f[a+1][b][c][d][e]+=f[a][b][c][d][e]
对于下面的则是，当b<k2且b<a，让f[a][b+1][c][d][e]+=f[a][b][c][d][e]
剩下的也是以此类推
附上代码
#include <iostream> #include <stdio.h> #include <algorithm> #include <cmath> #include <math.h> #include <string.h> #define ll long long using namespace std; inline int read() { char c=getchar();int a=0,b=1; for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1; for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b; } int k[6],n,tot; int main() { while(n=read()) { if(n==0)break; tot=0; memset(k,0,sizeof(k)); for(int i=1;i<=n;i++) k[i]=read(),tot+=k[i]; unsigned ll f[k[1]+1][k[2]+1][k[3]+1][k[4]+1][k[5]+1]; memset(f,0,sizeof(f)); f[0][0][0][0][0]=1; for(int k1=0;k1<=k[1];k1++) { for(int k2=0;k2<=k[2];k2++) { for(int k3=0;k3<=k[3];k3++) { for(int k4=0;k4<=k[4];k4++) { for(int k5=0;k5<=k[5];k5++) { if(k1<k[1])f[k1+1][k2][k3][k4][k5]+=f[k1][k2][k3][k4][k5]; if(k2<k1&&k2<k[2])f[k1][k2+1][k3][k4][k5]+=f[k1][k2][k3][k4][k5]; if(k3<k2&&k3<k[3])f[k1][k2][k3+1][k4][k5]+=f[k1][k2][k3][k4][k5]; if(k4<k3&&k4<k[4])f[k1][k2][k3][k4+1][k5]+=f[k1][k2][k3][k4][k5]; if(k5<k4&&k5<k[5])f[k1][k2][k3][k4][k5+1]+=f[k1][k2][k3][k4][k5]; } } } } }//我在干什么？ cout<<f[k[1]][k[2]][k[3]][k[4]][k[5]]<<endl; } return 0; }
这个空间真的是。。。
魔幻
这题主要是这个计数，我之前好像总结过？有点印象，但是已经过去太久了，忘记了。
一个主要的点就是，对于每一道题目，都要分析一下题目的特征或者说是特性，这是解题的关键，也是题目的难点（一般来说）
而这种加法来计数的，也就是这一类构造题目的一个解题方向
也是应该从中积累和学习到的东西