admin 管理员组

文章数量: 893620

P07748. 义务植树

P07748. 义务植树

Description

3月12日植树节到了,小明的班主任带着全班同学到白云山义务植树。小明心里想还没有去过白云山呢,这下可以好好玩一下。好不容易到了白云山,找到预先安排好的地方,班主任把工具分发下去,拿出一张图纸(如图1)展示给大家看,并说明要求: 我们班所有同学植的树要成一个等腰三角形,等腰三角形的两条腰上按顺序都是植1棵树,其他位置植树棵数等于它的左上角和右上角所植树的和。全班同学一定不能弄错,要分工协作,发扬团结互助的精神,把这次植树活动做好。 小明负责本小组植树棵数的计算,例如第i行第j个位置应植多少棵树。小明认真看了一下图纸,傻眼了,这该怎么计算啊?原来还想好好玩一玩,这下可惨了。你能帮助小明完成计算任务吗?

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

Input

输入只有1行: i i i和 j j j两个数, 1 ≤ i , j ≤ 101 1\leq i,j\leq101 1≤i,j≤101, j ≤ i j\leq i j≤i,中间隔一个空格,表示植树位置为第i行第j个位置(从左往右数第j个)。

Output

输出文件只有一个数:所求位置上应植树的棵数。

Samples

输入数据 1
3 2
输出数据 1
2
输入数据 2
5 3
输出数据 2
6

思路

树的棵数实际上是个杨辉三角,但数据范围表示,就算用double类型也会爆,所以只能用高精。。。

CODE

#include<bits/stdc++.h>
using namespace std;
int h,l,len,len1;
int a[110][110][1000],t[110][110];//树棵数每一位、总位数
int main(){scanf("%d%d",&h,&l);for(int i=1;i<=h;i++){//为每一行第一个和最后一个赋初值a[i][1][1]=a[i][i][1]=1;t[i][1]=t[i][i]=1;}for(int i=3;i<=h;i++)for(int j=2;j<i;j++){len=max(t[i-1][j-1],t[i-1][j]);//高精加for(int k=1;k<=len;k++){a[i][j][k]+=a[i-1][j-1][k]+a[i-1][j][k];a[i][j][k+1]=a[i][j][k]/10;a[i][j][k]%=10;}if(a[i][j][len+1])len++;t[i][j]=len;}for(int k=t[h][l];k>=1;k--)cout<<a[h][l][k];return 0;
}

本文标签: P07748 义务植树