首页 > 代码库 > codevs 1255 搭积木 x
codevs 1255 搭积木 x
1255 搭积木
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 Description
一种积木搭建方式，高为H的积木，最底层有M个积木，每一层的积木数是他的低一层的积木数+1或-1。总共有N个积木。（且每行积木数不超过10）
比如下图N=13 H=6 M=2。
输入描述 Input Description
第一行为三个整数、N、H、M。
第二行以后每行一个整数K，-1为结束符。
输出描述 Output Description
第一行为满足N、H、M的积木搭建方案总数（1<=N<=540 H<=60 M<=10）
以后每一行对于对应的K，给出顺序排列的第K种方案（最小的排列为第一种）。
（如样例中，2 1 2 3 2 3是一种方案，代表一层的积木分别为212323，232321也是一种方案，212323比232321要小，每个状态之间是可比的，第一个数小的排前面，第一个数相等的就看第二个数。那么所有方案就有一个顺序了，这里的K就是求第K个按顺序排列的方案）
样例输入 Sample Input
13 6 2
1
3
-1
样例输出 Sample Output
3
2 1 2 3 2 3
2 3 2 3 2 1
思路:
其实有两种思路,一种是DP,另一种就是记忆化搜索.
坑点:
在记忆化搜索时,剪枝是必不可少的!最优剪枝应该是当 n/h>10 或者是 n/h<1 时,是绝对不可能的!搜索速度大大提高!
代码:
这里暂时先给出记忆化搜索的代码~
/*作者:狐白酒(my name on the codevs!)题目:p1255 搭积木*/#include <iostream>#include <cstdio>#define LL long longusing namespace std;int N,H,M;bool v[62][542][12];LL f[62][542][12];LL dfs(int h,int n,int m)///high,sum,down{ if(n/h>10 || n/h<1) return f[h][n][m]=0;///这里剪枝剪的特多~ if(v[h][n][m]) return f[h][n][m]; else { if(h==1) { v[h][n][m]=1; if(n==m && m<=10) return f[h][n][m]=1; else return f[h][n][m]=0; } if(h>=2) { LL s=0; if(m-1>=1) s+=dfs(h-1,n-m,m-1); if(m+1<=10) s+=dfs(h-1,n-m,m+1); v[h][n][m]=1; return f[h][n][m]=s; } }}void ask(LL x,int h,int n,int m){ printf("%d ",m); if(h>=2) { if(x<=f[h-1][n-m][m-1]) ask(x,h-1,n-m,m-1); else ask(x-f[h-1][n-m][m-1],h-1,n-m,m+1); }}int main(){ scanf("%d%d%d",&N,&H,&M); dfs(H,N,M); cout<<f[H][N][M]<<endl; LL k; while(cin>>k) { if(k==-1) break; ask(k,H,N,M); printf("\n"); } return 0;}
过几天再把动规的补上~
End.
codevs 1255 搭积木 x
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。