小明最近喜欢搭数字积木， 一共有10块积木，每个积木上有一个数字，0~9。 搭积木规则： 每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。 最后搭成4层的金字塔形，必须用完所有的积木。
下面是两种合格的搭法： 0 1 2 3 4 5 6 7 8 9
0 3 1 7 5 2 9 8 6 4 请你计算这样的搭法一共有多少种？
请填表示总数目的数字。
思路：
用c++的STL写这种提交答案的题再好不过了，快准狠啊
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; int main() { int a[10]={0,1,2,3,4,5,6,7,8,9},cnt=0; do { if ((a[0]<a[1]&&a[0]<a[2]) && (a[1]<a[3]&&a[1]<a[4]) && (a[2]<a[4]&&a[2]<a[5]) && (a[3]<a[6]&&a[3]<a[7])&& (a[4]<a[7]&&a[4]<a[8])&& (a[5]<a[8]&&a[5]<a[9]) ) { cnt++; } }while (next_permutation(a,a+10)); cout<<cnt; return 0; } 用深搜的方法： #include<iostream> #include<cstdio> using namespace std; int a[10],v[10]={0},cnt=0; void dfs(int x) { int i; if (x >10) return ; if (x == 10) { if ((a[0]<a[1]&&a[0]<a[2]) && (a[1]<a[3]&&a[1]<a[4]) && (a[2]<a[4]&&a[2]<a[5]) && (a[3]<a[6]&&a[3]<a[7])&& (a[4]<a[7]&&a[4]<a[8])&& (a[5]<a[8]&&a[5]<a[9]) ) { cnt++; } return ; } for (i=0; i<10; i++) { if (!v[i]) { a[x] = i; v[i] = 1; dfs(x+1); v[i] = 0; } } } int main() { dfs(0); cout<<cnt; return 0; } 上面两种方法运行时间都差不多，在通过给深搜优化，缩短时间 #include<iostream> #include<cstdio> using namespace std; int a[10],v[10]={0},cnt=0; void dfs(int x) { int i; if (x>10) return ; else if (x == 3) { if (a[0]>a[1]|| a[0]>a[2]) return ; } else if (x == 6) { if (a[1]>a[3] || a[1]>a[4] || a[2]>a[4] || a[2]>a[5]) return ; } else if (x == 10) { if (a[3]>a[6] || a[3]>a[7] || a[4]>a[7] || a[4]>a[8] || a[5]>a[8] || a[5]>a[9]) return ; cnt++; } for (i=0; i<10; i++) { if (!v[i]) { a[x] = i; v[i] = 1; dfs(x+1); v[i] = 0; } } } int main() { dfs(0); cout<<cnt; return 0; }