XJOI1657&Codevs1255搭积木【树状动规】
2024-08-27 13:21:30
搭积木
一种积木搭建方式,高为H的积木,最底层有M个积木,每一层的积木数是他的低一层的积木数+1或-1。总共有N个积木。(且每行积木数不超过10)
比如上图N=13 H=6 M=2。
输入格式:
第一行为三个整数、N、H、M。
第二行以后每行一个整数K,-1为结束符。
输出格式:
第一行为满足N、H、M的积木搭建方案总数(1<=N<=540 H<=60 M<=10)
以后每一行对于对应的K,给出顺序排列的第K种方案(最小的排列为第一种)。
样例输入:
13 6 2 1 3 -1
样例输出:
3 2 1 2 3 2 3 2 3 2 3 2 1
时间限制:
1000
初次看这题竟不易想到树状动规,毕竟输出路径实在太容易想到暴搜了,但是事实证明动规是对的
f[i][j][k]是指堆到第i层,第i层堆j个,共用了k个
f[i][j][k]=f[i-1][j-1][k-j]+f[i-1][j+1][k-j]
边界:f[1][i][i]=1;
路径打印:若x大于f[i][j-1][k-i],则x-=f[i][j-1][k-i],打出当前搜索到的行,然后下一层搜索
#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,h,m; ][][],qst; inline void work(long long x,int h,int now,int a) { printf("%d ",now); ) return; a-=now; ][now-][a]) { x-=f[h-][now-][a]; now++; } else now--; work(x,h-,now,a); return; } int main() { scanf("%d%d%d",&n,&h,&m); ;i<=min(h+m-,);i++) f[][i][i]=; ;i<=h;i++) ;j<=min(h+m-,);j++) ;k<=n;k++) f[i][j][k]=f[i-][j-][k-j]+f[i-][j+][k-j]; printf("%lld",f[h][m][n]); ) { scanf("%lld",&qst); ) break; printf("\n"); work(qst,h,m,n); } ; }
最新文章
- mogodb监控脚本
- LeetCode之Largest Rectangle in Histogram浅析
- purgeIdleCellConnections: found one to purge conn = 0x1e09f7d0
- 前端工程搭建NodeJs+gulp+bower
- MVC 路由Router
- 仿新浪微博短网址PHP实现方案
- 深入Callable及Runnable两个接口 获取线程返回结果
- Spring的原理性总结
- Python迭代器与格式化
- JavaScript 排序算法
- 每天学习SQL
- JAVA框架Struts2(二)
- RabbitMQ文档翻译——Hello World!(上)
- (原)linux下利用cmake来编译jthread开源库
- 爬虫之BeautifulSoup
- SpringBoot 整合swagger
- Codeforces Beta Round #5 A. Chat Server&#39;s Outgoing Traffic 水题
- [Todo]很不错的Java面试题类型整理,要看
- jquery ajax 超时设置
- [SoapUI] context.expand 和 groovyUtils.getXmlHolder 有什么不一样