2013
12-21

# Distribute Message

The contest’s message distribution is a big thing in prepare. Assuming N students stand in a row, from the row-head start transmit message, each person can transmit message to behind M personals, and how many ways could row-tail get the message?

Input may contain multiple test cases. Each case contains N and M in one line. (0<=M<N<=30)
When N=0 and M=0, terminates the input and this test case is not to be processed.

Output the ways of the Nth student get message.

4 1
4 2
0 0

1
3
Hint

4 1 : A->B->C->D 4 2 : A->B->C->D, A->C->D, A->B->D

1.题目

http://acm.hdu.edu.cn/showproblem.php?pid=1723

2.分析

3.复杂度

4.涉及内容

5.感想

6.代码

#include <iostream>
using namespace std;
long f[31];
#define min(a,b) (a>b?b:a)
int main()
{
//freopen("in.txt","r",stdin);
int M,N;
while(cin>>N>>M,!(N==0&&M==0))
{
memset(f,0,sizeof(f));
f[0]=0;f[1]=1;
for(int i=2;i<=N;++i)
{
for(int k=1;k<=min(M,i);++k)
f[i]+=f[i-k];
}
cout<<f[N]<<endl;
}
return 0;
}

1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。