堆放木块C++实现
堆放木块是题很有意思的题目，原题的描述为：
我们用2维数组n[i][j] 表示平面上凸起的高度。或者说在二维平面上堆放立方体，满足 （每个数组元素都是非负整数）
n[i][j] <= n[i][j+1] n[i][j] <= n[i+1][j]
之前我就分析过了，这题与ferrers图有很大的联系，再看看Ferrers图：
ferrers图是一个从上而下的n层格子，mi 为第i层的格子数，当mi>=mi+1(i=1,2,,n-1) ，即上层的格子数不少于下层的格子数的图。
如下是一些ferrers图：
所以，可以看到，每个合理的摆放每一层都是一个ferrers图，且下层图的格子数不能比上层的格子数小，即每一列都不能小，然后至多堆放c层，这样，思路就有了
因为我不会写java，所以我先用c++实现打了个表，下面是我的C++代码实现;
/*******************************************************************************/
/* OS : Linux fc20.x86_64 #1 SMP Tue Dec UTC 2013 x86_64 GNU/Linux
* Compiler : 4.8.2 20131212 (Red Hat 4.8.2-7) (GCC)
* Encoding : UTF8
* Date : 2014-03-21
* All Rights Reserved by alop.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
long long D[7][7][7][7][7][7][7];
int main(){
freopen("in.txt","w",stdout);
int a[7],b[7];
for(a[1]=1;a[1]<7;a[1]++)
for(a[2]=0;a[2]<=a[1];a[2]++)
for(a[3]=0;a[3]<=a[2];a[3]++)
for(a[4]=0;a[4]<=a[3];a[4]++)
for(a[5]=0;a[5]<=a[4];a[5]++)
for(a[6]=0;a[6]<=a[5];a[6]++)
D[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][1]=1;
for(int i=2;i<=6;i++)
for(a[1]=1;a[1]<7;a[1]++)
for(a[2]=0;a[2]<=a[1];a[2]++)
for(a[3]=0;a[3]<=a[2];a[3]++)
for(a[4]=0;a[4]<=a[3];a[4]++)
for(a[5]=0;a[5]<=a[4];a[5]++)
for(a[6]=0;a[6]<=a[5];a[6]++)
{
D[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][i]=0;
for(b[1]=1;b[1]<=a[1];b[1]++)
for(b[2]=0;b[2]<=min(b[1],a[2]);b[2]++)
for(b[3]=0;b[3]<=min(b[2],a[3]);b[3]++)
for(b[4]=0;b[4]<=min(b[3],a[4]);b[4]++)
for(b[5]=0;b[5]<=min(b[4],a[5]);b[5]++)
for(b[6]=0;b[6]<=min(b[5],a[6]);b[6]++)
D[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][i]+= D[b[1]][b[2]][b[3]][b[4]][b[5]][b[6]][i-1];
}
for(int c=1;c<=6;c++)
{
long long fer=1;
for(int d=1;d<=6;d++)
{
for(a[1]=1;a[1]<=d;a[1]++)
for(int i=1;i<=c;i++)
fer+= D[a[1]][0][0][0][0][0][i];
cout<<"fs["<<d<<"][1]["<<c<<"]="<<fer<<"L ;";
fer=1;
}
cout<<endl;
for(int d=1;d<=6;d++)
{
for(a[1]=1;a[1]<=d;a[1]++)
for(a[2]=0;a[2]<=a[1];a[2]++)
for(int i=1;i<=c;i++)
fer+= D[a[1]][a[2]][0][0][0][0][i];
cout<<"fs["<<d<<"][2]["<<c<<"]="<<fer<<"L; ";
fer=1;
}
cout<<endl;
for(int d=1;d<=6;d++)
{
for(a[1]=1;a[1]<=d;a[1]++)
for(a[2]=0;a[2]<=a[1];a[2]++)
for(a[3]=0;a[3]<=a[1];a[3]++)
for(int i=1;i<=c;i++)
fer+= D[a[1]][a[2]][a[3]][0][0][0][i];
cout<<"fs["<<d<<"][3]["<<c<<"]="<<fer<<"L ; ";
fer=1;
}
cout<<endl;
for(int d=1;d<=6;d++)
{
for(a[1]=1;a[1]<=d;a[1]++)
for(a[2]=0;a[2]<=a[1];a[2]++)
for(a[3]=0;a[3]<=a[1];a[3]++)
for(a[4]=0;a[4]<=a[3];a[4]++)
for(int i=1;i<=c;i++)
fer+= D[a[1]][a[2]][a[3]][a[4]][0][0][i];
cout<<"fs["<<d<<"][4]["<<c<<"]="<<fer<<"L ;";
fer=1;
}
cout<<endl;
for(int d=1;d<=6;d++)
{
for(a[1]=1;a[1]<=d;a[1]++)
for(a[2]=0;a[2]<=a[1];a[2]++)
for(a[3]=0;a[3]<=a[1];a[3]++)
for(a[4]=0;a[4]<=a[3];a[4]++)
for(a[5]=0;a[5]<=a[4];a[5]++)
for(int i=1;i<=c;i++)
fer+= D[a[1]][a[2]][a[3]][a[4]][a[5]][0][i];
cout<<"fs["<<d<<"][5]["<<c<<"]="<<fer<<"L ;";
fer=1;
}
cout<<endl;
for(int d=1;d<=6;d++)
{
for(a[1]=1;a[1]<=d;a[1]++)
for(a[2]=0;a[2]<=a[1];a[2]++)
for(a[3]=0;a[3]<=a[1];a[3]++)
for(a[4]=0;a[4]<=a[3];a[4]++)
for(a[5]=0;a[5]<=a[4];a[5]++)
for(a[6]=0;a[6]<=a[5];a[6]++)
for(int i=1;i<=c;i++)
fer+= D[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][i];
cout<<"fs["<<d<<"][6]["<<c<<"]="<<fer<<"L ;";
fer=1;
}
cout<<endl;
}
return 0;
fclose(stdout);
}可以看到，我写了超多的for循环，但其实思路是很清晰的，就是ferrers图的层层叠加；下面是输出数据：
fs[1][1][1]=2L ;fs[2][1][1]=3L ;fs[3][1][1]=4L ;fs[4][1][1]=5L ;fs[5][1][1]=6L ;fs[6][1][1]=7L ;
fs[1][2][1]=3L; fs[2][2][1]=6L; fs[3][2][1]=10L; fs[4][2][1]=15L; fs[5][2][1]=21L; fs[6][2][1]=28L;
fs[1][3][1]=4L ; fs[2][3][1]=10L ; fs[3][3][1]=20L ; fs[4][3][1]=35L ; fs[5][3][1]=56L ; fs[6][3][1]=84L ;
fs[1][4][1]=5L ;fs[2][4][1]=15L ;fs[3][4][1]=35L ;fs[4][4][1]=70L ;fs[5][4][1]=126L ;fs[6][4][1]=210L ;
fs[1][5][1]=6L ;fs[2][5][1]=21L ;fs[3][5][1]=56L ;fs[4][5][1]=126L ;fs[5][5][1]=252L ;fs[6][5][1]=462L ;
fs[1][6][1]=7L ;fs[2][6][1]=28L ;fs[3][6][1]=84L ;fs[4][6][1]=210L ;fs[5][6][1]=462L ;fs[6][6][1]=924L ;
fs[1][1][2]=3L ;fs[2][1][2]=6L ;fs[3][1][2]=10L ;fs[4][1][2]=15L ;fs[5][1][2]=21L ;fs[6][1][2]=28L ;
fs[1][2][2]=6L; fs[2][2][2]=20L; fs[3][2][2]=50L; fs[4][2][2]=105L; fs[5][2][2]=196L; fs[6][2][2]=336L;
fs[1][3][2]=10L ; fs[2][3][2]=50L ; fs[3][3][2]=175L ; fs[4][3][2]=490L ; fs[5][3][2]=1176L ; fs[6][3][2]=2520L ;
fs[1][4][2]=15L ;fs[2][4][2]=105L ;fs[3][4][2]=490L ;fs[4][4][2]=1764L ;fs[5][4][2]=5292L ;fs[6][4][2]=13860L ;
fs[1][5][2]=21L ;fs[2][5][2]=196L ;fs[3][5][2]=1176L ;fs[4][5][2]=5292L ;fs[5][5][2]=19404L ;fs[6][5][2]=60984L ;
fs[1][6][2]=28L ;fs[2][6][2]=336L ;fs[3][6][2]=2520L ;fs[4][6][2]=13860L ;fs[5][6][2]=60984L ;fs[6][6][2]=226512L ;
fs[1][1][3]=4L ;fs[2][1][3]=10L ;fs[3][1][3]=20L ;fs[4][1][3]=35L ;fs[5][1][3]=56L ;fs[6][1][3]=84L ;
fs[1][2][3]=10L; fs[2][2][3]=50L; fs[3][2][3]=175L; fs[4][2][3]=490L; fs[5][2][3]=1176L; fs[6][2][3]=2520L;
fs[1][3][3]=20L ; fs[2][3][3]=175L ; fs[3][3][3]=980L ; fs[4][3][3]=4116L ; fs[5][3][3]=14112L ; fs[6][3][3]=41580L ;
fs[1][4][3]=35L ;fs[2][4][3]=490L ;fs[3][4][3]=4116L ;fs[4][4][3]=24696L ;fs[5][4][3]=116424L ;fs[6][4][3]=457380L ;
fs[1][5][3]=56L ;fs[2][5][3]=1176L ;fs[3][5][3]=14112L ;fs[4][5][3]=116424L ;fs[5][5][3]=731808L ;fs[6][5][3]=3737448L ;
fs[1][6][3]=84L ;fs[2][6][3]=2520L ;fs[3][6][3]=41580L ;fs[4][6][3]=457380L ;fs[5][6][3]=3737448L ;fs[6][6][3]=24293412L ;
fs[1][1][4]=5L ;fs[2][1][4]=15L ;fs[3][1][4]=35L ;fs[4][1][4]=70L ;fs[5][1][4]=126L ;fs[6][1][4]=210L ;
fs[1][2][4]=15L; fs[2][2][4]=105L; fs[3][2][4]=490L; fs[4][2][4]=1764L; fs[5][2][4]=5292L; fs[6][2][4]=13860L;
fs[1][3][4]=35L ; fs[2][3][4]=490L ; fs[3][3][4]=4116L ; fs[4][3][4]=24696L ; fs[5][3][4]=116424L ; fs[6][3][4]=457380L ;
fs[1][4][4]=70L ;fs[2][4][4]=1764L ;fs[3][4][4]=24696L ;fs[4][4][4]=232848L ;fs[5][4][4]=1646568L ;fs[6][4][4]=9343620L ;
fs[1][5][4]=126L ;fs[2][5][4]=5292L ;fs[3][5][4]=116424L ;fs[4][5][4]=1646568L ;fs[5][5][4]=16818516L ;fs[6][5][4]=133613766L ;
fs[1][6][4]=210L ;fs[2][6][4]=13860L ;fs[3][6][4]=457380L ;fs[4][6][4]=9343620L ;fs[5][6][4]=133613766L ;fs[6][6][4]=1447482465L ;
fs[1][1][5]=6L ;fs[2][1][5]=21L ;fs[3][1][5]=56L ;fs[4][1][5]=126L ;fs[5][1][5]=252L ;fs[6][1][5]=462L ;
fs[1][2][5]=21L; fs[2][2][5]=196L; fs[3][2][5]=1176L; fs[4][2][5]=5292L; fs[5][2][5]=19404L; fs[6][2][5]=60984L;
fs[1][3][5]=56L ; fs[2][3][5]=1176L ; fs[3][3][5]=14112L ; fs[4][3][5]=116424L ; fs[5][3][5]=731808L ; fs[6][3][5]=3737448L ;
fs[1][4][5]=126L ;fs[2][4][5]=5292L ;fs[3][4][5]=116424L ;fs[4][4][5]=1646568L ;fs[5][4][5]=16818516L ;fs[6][4][5]=133613766L ;
fs[1][5][5]=252L ;fs[2][5][5]=19404L ;fs[3][5][5]=731808L ;fs[4][5][5]=16818516L ;fs[5][5][5]=267227532L ;fs[6][5][5]=3184461423L ;
fs[1][6][5]=462L ;fs[2][6][5]=60984L ;fs[3][6][5]=3737448L ;fs[4][6][5]=133613766L ;fs[5][6][5]=3184461423L ;fs[6][6][5]=55197331332L ;
fs[1][1][6]=7L ;fs[2][1][6]=28L ;fs[3][1][6]=84L ;fs[4][1][6]=210L ;fs[5][1][6]=462L ;fs[6][1][6]=924L ;
fs[1][2][6]=28L; fs[2][2][6]=336L; fs[3][2][6]=2520L; fs[4][2][6]=13860L; fs[5][2][6]=60984L; fs[6][2][6]=226512L;
fs[1][3][6]=84L ; fs[2][3][6]=2520L ; fs[3][3][6]=41580L ; fs[4][3][6]=457380L ; fs[5][3][6]=3737448L ; fs[6][3][6]=24293412L ;
fs[1][4][6]=210L ;fs[2][4][6]=13860L ;fs[3][4][6]=457380L ;fs[4][4][6]=9343620L ;fs[5][4][6]=133613766L ;fs[6][4][6]=1447482465L ;
fs[1][5][6]=462L ;fs[2][5][6]=60984L ;fs[3][5][6]=3737448L ;fs[4][5][6]=133613766L ;fs[5][5][6]=3184461423L ;fs[6][5][6]=55197331332L ;
fs[1][6][6]=924L ;fs[2][6][6]=226512L ;fs[3][6][6]=24293412L ;fs[4][6][6]=1447482465L ;fs[5][6][6]=55197331332L ;fs[6][6][6]=1478619421136L ;
就这样，这题就完美解决了！
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
