题目链接：http://poj.org/problem?id=2279
题意：给出一个n行的矩阵，每一行有a[i]个数，总共有sum个数，要求每一个位置的数必须比上面的数和左面的数大，求总方案数
题解：
刚开始看到这道题，潜意识里是要爆搜（貌似我也只会这样做了）
毕竟暴力出滑稽
但貌似有DP解法？？？（听lyd讲了还是不会啊）
只好强势安利一个【杨氏矩阵/钩子公式】了
以下部分转自 ACdreamers
杨氏矩阵又叫杨氏图表，它是这样一个矩阵，满足条件：
(1)如果格子(i,j)没有元素，则它右边和上边的相邻格子也一定没有元素。
(2)如果格子(i,j)有元素a[i][j]，则它右边和上边的相邻格子要么没有元素，要么有元素且比a[i][j]大。
1 ~ n所组成杨氏矩阵的个数可以通过下面的递推式得到：
下面介绍一个公式，那就是著名的钩子公式。
对于给定形状，不同的杨氏矩阵的个数为：n！/(每个格子的钩子长度加1的积)。
其中钩子长度定义为该格子右边的格子数和它上边的格子数之和。
证明的话……
只好挖个坑了
路过了大佬如果知道的话麻烦指教一下蒟蒻
回到这道题目
就是把杨氏矩阵转了个圈
直接套用公式就好了
但为了防止中间结果溢出要步步约分
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
int n,num[10],tot;
LL t1,t2,tmp[110],hhh;
LL gcd(LL a,LL b)
{return b?gcd(b,a%b):a;
}
int main()
{while(scanf("%d",&n)&&n){memset(tmp,0,sizeof(tmp));t1=1,t2=1,tot=0;for(int i=1;i<=n;i++)scanf("%d",&num[i]);for(int i=1;i<=n;i++)for(int j=1;j<=num[i];j++){tmp[++tot]+=num[i]-j+1;for(int k=i+1;k<=n;k++) tmp[tot]+=(num[k]>=j);}for(int i=1;i<=tot;i++){t1*=i;t2*=tmp[i];hhh=gcd(t1,t2);t1/=hhh;t2/=hhh; }printf("%lld\n",t1/t2);}return 0;
}听说POJ1825是双倍经验题（手动滑稽）