刚开始我以为是f[i][j]表示i行j列满足条件的方案数,但是发现没办法表示。看完讲解之后,明白了五维dp的原因。
因为之前做的题都是从一个小的状态转变到另外一个小的状态,所以我直接就忽略了完全可以把整体的排列方式看作一个状态,然后向后更新状态,这也就是“由一个已知状态,思考可以更新哪些未知状态”。
因此就可以使用五维dp表示每个整体排列的方案数。
为什么是五位状态?因为题中k的范围是小于等于5。五维dp,把不同的总体排队方式当作不同的集合,求每个集合的方案数。
f[a][b][c][d][e]表示第一排有a个人,第二排有b个人…第5排有e个人。
多组输入,注意初始化。
#include <bits/stdc++.h>
using namespace std;
const int N=32,M=7;
typedef long long ll;
typedef pair<int,int> pii;
int h[N],e[M],ne[M],w[M],idx;
void add(int x,int y,int c) //初始化h为-1
{
e[idx]=y;ne[idx]=h[x];w[idx]=c;h[x]=idx++;
}
ll f[N][N][N][N][N];
int n,a[10];
int main()
{
while(cin>>n,n)
{
memset(a,0,sizeof a);
for(int i=1;i<=n;i++)cin>>a[i];
memset(f,0,sizeof f);
f[0][0][0][0][0]=1;
for(int i=0;i<=a[1];i++)
for(int j=0;j<=min(i,a[2]);j++)
for(int k=0;k<=min(j,a[3]);k++)
for(int t=0;t<=min(k,a[4]);t++)
for(int h=0;h<=min(t,a[5]);h++)
{
ll &x=f[i][j][k][t][h];
if(i&&i-1>=j)x+=f[i-1][j][k][t][h];
if(j&&j-1>=k)x+=f[i][j-1][k][t][h];
if(k&&k-1>=t)x+=f[i][j][k-1][t][h];
if(t&&t-1>=h)x+=f[i][j][k][t-1][h];
if(h)x+=f[i][j][k][t][h-1];
}
cout<<f[a[1]][a[2]][a[3]][a[4]][a[5]]<<endl;
}
return 0;
}
278