锐客网

  1. 首页 > it技术 > >

[线性DP][杨氏矩阵和勾长公式]Mr.|[线性DP][杨氏矩阵和勾长公式]Mr. Young's Picture Permutations

传送门

描述 有n个学生合影，站成左对齐的k排，每行分别有N1,N2…NK个人，第一排站最后，第k排站之前。
学生身高依次是1…N。在合影时候要求每一排从左到右递减，每一列从后面到前也递减，一共有多少总方案
输入
每组测试数据包含两行。第一行给出行数k。
【[线性DP][杨氏矩阵和勾长公式]Mr.|[线性DP][杨氏矩阵和勾长公式]Mr. Young's Picture Permutations】第二行包含从后到前（n1，n2，…，nk）的行的长度，作为由单个空格分隔的十进制整数。
问题数据以0结束。
行数 不会超过5行，学生总数N 最多为30。
输出 输出每组数据的方案数
样例输入
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 ] f[i][j][k][l][m] f[i][j][k][l][m]为第一排站i个，第二排站j个……的方案数
如果i 代码：
#include using namespace std; int k,n[10],a[10]; int main() { while(scanf("%d",&k),k!=0) { memset(n,0,sizeof(n)); for(int i=1; i<=k; i++) scanf("%d",&n[i]); unsigned f[n[1]+1][n[2]+1][n[3]+1][n[4]+1][n[5]+1]; memset(f,0,sizeof(f)); f[0][0][0][0][0]=1; for(a[1]=0; a[1]<=n[1]; a[1]++) for(a[2]=0; a[2]<=n[2]; a[2]++) for(a[3]=0; a[3]<=n[3]; a[3]++) for(a[4]=0; a[4]<=n[4]; a[4]++) for(a[5]=0; a[5]<=n[5]; a[5]++) { int tmp=f[a[1]][a[2]][a[3]][a[4]][a[5]]; if(a[1]

第二种：杨氏矩阵和勾长公式：
杨氏矩阵又叫杨氏图表，它是这样一个矩阵，满足条件：
(1)如果格子(i,j)没有元素，则它右边和上边的相邻格子也一定没有元素。
(2)如果格子(i,j)有元素 a [ i ] [ j ] a[i][j] a[i][j]，则它右边和上边的相邻格子要么没有元素，要么有元素且比 a [ i ] [ j ] a[i][j] a[i][j]大。
1 ~ n所组成杨氏矩阵的个数可以通过下面的递推式得到：
[线性DP][杨氏矩阵和勾长公式]Mr.|[线性DP][杨氏矩阵和勾长公式]Mr. Young's Picture Permutations
文章图片

如图就是n=3时的杨氏矩阵。
[线性DP][杨氏矩阵和勾长公式]Mr.|[线性DP][杨氏矩阵和勾长公式]Mr. Young's Picture Permutations
文章图片

下面介绍一个公式，那就是著名的钩子公式。
对于给定形状，不同的杨氏矩阵的个数为：n！除以每个格子的钩子长度加1的积。其中钩子长度定义为该格子右边的格子数和它上边的格子数之和。
那么这道题就是公式题了
代码:
#include #define ll long long using namespace std; int n; ll a[10],tot=0,hook=1,ans=1; ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b); } void get_hook(){ for(int i=n; i>=1; i--){ for(int j=1; j<=a[i]; j++){ ll cnt=a[i]-j+1; for(int k=n; k>i; k--) if(a[k]>=j) cnt++; hook*=cnt; ans*=++tot; ll gcdd=gcd(ans,hook); ans/=gcdd; hook/=gcdd; } } } int main(){ while(scanf("%d",&n)){ if(n==0) break; for(int i=1; i<=n; i++) scanf("%d",&a[i]); ans=1,hook=1,tot=0; get_hook(); cout<

    推荐阅读


    上一篇：主席树|191101CSP模拟题解

    下一篇：B - Divples Gym - 102302B