Exam 4894 Booming Business

4894: Booming Business

时间限制: 1 Sec  内存限制: 128 MB
提交: 34  解决: 9
[提交] [状态] [讨论版] [命题人:admin]

题目描述

You are an expert in bonsai, the Japanese art of cultivating small trees in small containers.Every year, you win the Bonsai Association’s Pruning Competition (BAPC). With all this talent, it would be a shame not to turn your hobby into your job. Recently, you have rented a small store where you will sell your creations. Now you need to make a window display to draw in customers. Of course, you would like to grow the most impressive tree that will fit the window, but the window is only so tall, and the floor of the display can only bear so much weight. Therefore, you want a tree that is exactly so tall and so heavy that it can fit in your window.
Being an expert, you know that by definition a bonsai tree consists of a single branch, with 0 or more smaller bonsai trees branching off from that branch.

figure 1: Four distinct examples of bonsai trees.

The height and weight of a bonsai tree can be carefully determined. A tree’s weight is equal to the number of branches that appear in it. The weights of the trees in figure 1 are 1, 4,6 and 6, respectively. A tree’s height is equal to the length of the longest chain of branches from the root to the top of the tree. The heights of the trees in figure 1 are 1, 2, 3 and 3,respectively.
To make the most use of your window, you want to produce a bonsai tree of the precise height and weight that it can support. To get an idea of the number of options available to you, you would like to know how many different trees you could possibly grow for your store. Given a height and a weight, can you determine the number of trees with exactly that height and weight? Because the number may be very large, you may give your answer modulo 1,000,000,007.

输入

A single line containing two integers, h and w, with 1 ≤ h, w ≤ 300.

输出

Output a single line containing a single integer, the number of bonsai trees of height h and weight w, modulo 109+7.

样例输入

2 4

样例输出

1

来源/分类

BAPC2017 Preliminaries 

 

思路：

取 f (i,j) 表示 高度上限为 i，边数为 j 的树的种类数。

 

观察会发现一棵高度上限为 i ，边数为 j 的树都可以拆成 一棵高度上限为 i-1，边数 k 的树与 高度上限为 i ，边数为 j-k 的树。（i-1是因为不考虑最下层的那一根）

 于是  f(i,j)=sum{ f(i-1,k)*f(i,j-k) } ,(1<= k < j)

 

则最终答案为 f(h,w)-f(h-1,w)。

 

代码如下：

#include <bits/stdc++.h>
#define rep(i,s,t) for (auto i=s; i<=t; i++)
typedef long long ll;
const int maxn=310,mod=1e9+7;
ll f[maxn][maxn];
int h,w;
int main(){
    std::cin>>h>>w;f[1][1]=1;
    rep(i,2,h){
        f[i][1]=1;
        rep(j,2,w) rep(k,1,j-1) (f[i][j]+=f[i-1][k]*f[i][j-k]%mod)%=mod;
    }
    return std::cout<<((f[h][w]-f[h-1][w])%mod+mod)%mod,0;
}