#动态规划 or 杨氏矩阵，勾长公式#poj 2279 Mr. Young's Picture Permutations

本文主要是介绍#动态规划 or 杨氏矩阵，勾长公式#poj 2279 Mr. Young's Picture Permutations，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

有n行，人数依次递减，而行内的顺序也是递减，问一共有多少种方案

---

（动态规划）分析

可以用一个5维dp，具体就是一次又一次增加，注意动态开内存

---

代码

#include <cstdio>
#include <cstring>
int n,a[5];
int in(){int ans=0; char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=ans*10+c-48,c=getchar();return ans;
}
int min(int a,int b){return (a<b)?a:b;}
int main(){while (1){if (!(n=in())) return 0; memset(a,0,sizeof(a));for (int i=0;i<n;i++) scanf("%d",&a[i]);unsigned f[a[0]+1][a[1]+1][a[2]+1][a[3]+1][a[4]+1];memset(f,0,sizeof(f)); f[0][0][0][0][0]=1;for (int i=0;i<=a[0];i++)for (int j=0;j<=min(i,a[1]);j++)for (int k=0;k<=min(j,a[2]);k++)for (int p=0;p<=min(k,a[3]);p++)for (int t=0;t<=min(p,a[4]);t++){unsigned num=f[i][j][k][p][t];if (i<a[0]) f[i+1][j][k][p][t]+=num;if (j<a[1]&&j<i) f[i][j+1][k][p][t]+=num;if (k<a[2]&&k<j&&k<i) f[i][j][k+1][p][t]+=num;if (p<a[3]&&p<k&&p<j&&p<i) f[i][j][k][p+1][t]+=num;if (t<a[4]&&t<p&&t<k&&t<j&&t<i) f[i][j][k][p][t+1]+=num;}printf("%u\n",f[a[0]][a[1]][a[2]][a[3]][a[4]]);}
}

---

#数学方法
1~n组成杨氏矩阵的个数可以写出：
$F[1]=1，F[2]=2，F[n]=F[n-1]+(n-1)\ast F[n-2](n>2)。$
钩子长度的定义：该格子右边的格子数和它上边的格子数之和;
钩子公式：对于给定形状，不同的杨氏矩阵的个数为($n!÷$(每个格子的钩子长度加1的积))。

---

#代码

#include <cstdio>
#include <cstring>
typedef unsigned uit;
uit n,a[5],num[31],tot;
uit in(){uit ans=0; char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=ans*10+c-48,c=getchar();return ans;
}
long long gcd(long long a,long long b){return (b)?gcd(b,a%b):a;}
int main(){while (1){if (!(n=in())) return 0; memset(a,0,sizeof(a));for (register uit i=0;i<n;i++) a[i]=in(); tot=0;for (register int i=n-1;i>=0;i--)for (register uit j=0;j<a[i];j++){num[++tot]=a[i]-j;for (register uit k=i+1;k<n;k++)if (a[k]>j) num[tot]++; else break;}long long ans1=1ll,ans2=1ll*num[1];for (register uit i=2;i<=tot;i++){ans1*=i; ans2*=num[i];long long t=gcd(ans1,ans2);//避免溢出ans1/=t; ans2/=t;}printf("%lld\n",ans1/ans2);}
}

这篇关于#动态规划 or 杨氏矩阵，勾长公式#poj 2279 Mr. Young's Picture Permutations的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---