首页 > 代码库 > XJOI1657&Codevs1255搭积木【树状动规】
XJOI1657&Codevs1255搭积木【树状动规】
搭积木
一种积木搭建方式,高为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],打出当前搜索到的行,然后下一层搜索
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 int n,h,m; 6 long long f[61][11][541],qst; 7 inline void work(long long x,int h,int now,int a) 8 { 9 printf("%d ",now); 10 if(h==1) return; 11 a-=now; 12 if(x>f[h-1][now-1][a]) 13 { 14 x-=f[h-1][now-1][a]; 15 now++; 16 } 17 else now--; 18 work(x,h-1,now,a); 19 return; 20 } 21 int main() 22 { 23 scanf("%d%d%d",&n,&h,&m); 24 for(int i=1;i<=min(h+m-1,10);i++) f[1][i][i]=1; 25 for(int i=2;i<=h;i++) 26 for(int j=1;j<=min(h+m-1,10);j++) 27 for(int k=1;k<=n;k++) f[i][j][k]=f[i-1][j-1][k-j]+f[i-1][j+1][k-j]; 28 printf("%lld",f[h][m][n]); 29 while(1) 30 { 31 scanf("%lld",&qst); 32 if(qst==-1) break; 33 printf("\n"); 34 work(qst,h,m,n); 35 } 36 return 0; 37 }
XJOI1657&Codevs1255搭积木【树状动规】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。