Mr. Young's Picture Permutations

雨点打透心脏的1/2处 2022-01-08 00:25 82阅读 0赞

[Mr. Young's Picture Permutations][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(); }

转载于:https://www.cnblogs.com/a1b3c7d9/p/10901422.html

[Mr. Young_s Picture Permutations]: http://poj.org/problem?id=2279