很明显的一个线性DP,对于$f[i][j][k][p][q]$,仅需满足$i\ge j\ge k\ge p\ge q$,如果要新插入一个点,这个点的编号是大于现存点的编号的,那么只要满足上面这个性质,就可以进行DP。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#define uint long long
#define gc getchar()
using namespace std;
const int N=31;
inline void qr(int &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
int a[6];uint f[31][31][31][31][31];
int main()
{
int n;
f[0][0][0][0][0]=1;
for(int i=0;i<=30;i++)
for(int j=0;j<=i;j++)
for(int k=0;k<=j;k++)
for(int p=0;p<=k;p++)
for(int q=0;q<=p;q++)
{
if(i<30)f[i+1][j][k][p][q]+=f[i][j][k][p][q];
if(j<i)f[i][j+1][k][p][q]+=f[i][j][k][p][q];
if(k<j)f[i][j][k+1][p][q]+=f[i][j][k][p][q];
if(p<k)f[i][j][k][p+1][q]+=f[i][j][k][p][q];
if(q<p)f[i][j][k][p][q+1]+=f[i][j][k][p][q];
}
while(qr(n),n)
{
for(int i=1;i<=n;i++)qr(a[i]);
for(int i=n+1;i<=5;i++)a[i]=0;
printf("%lld\n",f[a[1]][a[2]][a[3]][a[4]][a[5]]);
}
return 0;
}
还有一个杨氏矩阵的勾长公式:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=6;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(ll x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int a[N];
int sum[31];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main()
{
int n;
while(qr(n),n)
{
a[0]=31;memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)qr(a[i]),a[i]=min(a[i],a[i-1]);
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=a[i];j++)
{
++cnt;
for(int k=i+1;k<=n;k++)
{
if(a[k]>=j)++sum[cnt];
else break;
}
sum[cnt]+=a[i]-j+1;
}
ll ans,a=1,b=1;
for(int i=cnt;i>=1;i--)
{
a*=i;b*=sum[i];
ll d=gcd(a,b);
if(d!=1)a/=d,b/=d;
}
ans=a/b;
qw(ans);puts("");
}
return 0;
}
最后一次更新于2019-10-14
0 条评论