首页 > ACM题库 > HDU-杭电 > Hdu 1723 Distribute Message-动态规划[解题报告] C++
2013
12-21

Hdu 1723 Distribute Message-动态规划[解题报告] C++

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.分析
类似于阶梯问题,只不过此处,当处理i的时候,决策前i-1个,即为min(M,i)

3.复杂度
时间复杂度O(N^2);空间复杂度O(N);

4.涉及内容
动态规划

5.感想
本道题让我想起了对于求单调递增子序列(LIS)中的O(NLogN)的优化思路:在积累的索引递增数组B[N]中不断查找第一个大于等于d[i]的位置即可。具体请看参考文献1.

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,比楼主的要快。