Mr. Young's Picture Permutations

给出一个有k列的网格图，以及每列图形的高度\(n_i\)，下端对齐，保证高度递减，设有n个网格，询问向其中填1~n保证每行每列单调递增的方案数，\(n\leq 30,k\leq 5\)。

解

事实上，注意到k很小，我们就可以暴力状态了，而要表现单调递增，故维护一个从左至右边矮的阶梯。

以有5列为例，设\(f[a][b][c][d][e]\)表示第1列已经填的数字高度为a，第二列高度为b，...，第5列的高度为e的，现在填到数字\(a+b+c+d+e\)方案数，并保证转移时\(a\geq b\geq c\geq d\geq e\)，于是当一个新的数字填的时候一定比所有的数字都要大，也不会有比它小的数字使其非法，故满足了题意。

有因为逆转移无用状态枚举过多，考虑顺转移，因此有

\[f[a+1][b][c][d][e]+=f[a][b][c][d][e]
\]

\[f[a][b+1][c][d][e]+=f[a][b][c][d][e]
\]

\[f[a][b][c+1][d][e]+=f[a][b][c][d][e]
\]

\[f[a][b][c][d+1][e]+=f[a][b][c][d][e]
\]

\[f[a][b][c][d][e+1]+=f[a][b][c][d][e]
\]

边界：\(f[0][0][0][0][0]=1\)，其余为0

答案：\(f[n_1][n_2][n_3][n_4][n_5]\)

参考代码：

阶段转移

#include <iostream>

#include <cstdio>

#include <cstring>

#define il inline

#define ri register

#define ll long long

using namespace std;

ll len[31],dp[31][16][11][8][7];

il void read(ll&);

 int main(){

    ll k,n;

    while(read(k),k){

        memset(len,0,sizeof(len));

        memset(dp,0,sizeof(dp)),dp[0][0][0][0][0]=1;

        for(ri ll i(1);i<=k;++i)read(len[i]);

        for(ri ll a,b,c,d,e(0);e<=len[5];++e)

            for(d=e;d<=len[4];++d)

                for(c=d;c<=len[3];++c)

                    for(b=c;b<=len[2];++b)

                        for(a=b;a<=len[1];++a){

                            if(a<len[1])dp[a+1][b][c][d][e]+=dp[a][b][c][d][e];

                            if(b<len[2])dp[a][b+1][c][d][e]+=dp[a][b][c][d][e];

                            if(c<len[3])dp[a][b][c+1][d][e]+=dp[a][b][c][d][e];

                            if(d<len[4])dp[a][b][c][d+1][e]+=dp[a][b][c][d][e];

                            if(e<len[5])dp[a][b][c][d][e+1]+=dp[a][b][c][d][e];

                        }

        printf("%lld\n",dp[len[1]][len[2]][len[3]][len[4]][len[5]]);

    }

    return 0;

}

il void read(ll &x){

    x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');

    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

}

dfs

#include <iostream>

#include <cstdio>

#include <cstring>

#define il inline

#define ri register

#define ll long long

using namespace std;

int len[6];

ll dp[31][16][11][8][7];

il void read(int&);

ll dfs(int,int,int,int,int);

int main(){

    int k;while(read(k),k){

        memset(len,0,sizeof(len));

        memset(dp,0,sizeof(dp)),dp[0][0][0][0][0]=1;

        for(ri int i(1);i<=k;++i)read(len[i]);

        printf("%lld\n",dfs(len[1],len[2],len[3],len[4],len[5]));

    }

    return 0;

}

ll dfs(int a,int b,int c,int d,int e){

    if(a<0||b<0||c<0||d<0||e<0)return 0;

    ll &opt=dp[a][b][c][d][e];if(opt)return opt;

    opt=dfs(a,b,c,d,e-1);

    if(d>e)opt+=dfs(a,b,c,d-1,e);

    if(c>d)opt+=dfs(a,b,c-1,d,e);

    if(b>c)opt+=dfs(a,b-1,c,d,e);

    if(a>b)opt+=dfs(a-1,b,c,d,e);

    return opt;

}

il void read(int &x){

    x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');

    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();

}

巴特西

Mr. Young's Picture Permutations

解

最新文章

热门文章