首页 > ACM题库 > HDU-杭电 > HDU 4165-Pills-动态规划-[解题报告]HOJ
2015
05-23

HDU 4165-Pills-动态规划-[解题报告]HOJ

Pills

问题描述 :

Aunt Lizzie takes half a pill of a certain medicine every day. She starts with a bottle that contains N pills.

On the first day, she removes a random pill, breaks it in two halves, takes one half and puts the other half back into the bottle.

On subsequent days, she removes a random piece (which can be either a whole pill or half a pill) from the bottle. If it is half a pill, she takes it. If it is a whole pill, she takes one half and puts the other half back into the bottle.

In how many ways can she empty the bottle? We represent the sequence of pills removed from the bottle in the course of 2N days as a string, where the i-th character is W if a whole pill was chosen on the i-th day, and H if a half pill was chosen (0 <= i < 2N). How many different valid strings are there that empty the bottle?

输入:

The input will contain data for at most 1000 problem instances. For each problem instance there will be one line of input: a positive integer N <= 30, the number of pills initially in the bottle. End of input will be indicated by 0.

输出:

The input will contain data for at most 1000 problem instances. For each problem instance there will be one line of input: a positive integer N <= 30, the number of pills initially in the bottle. End of input will be indicated by 0.

样例输入:

6
1
4
2
3
30
0

样例输出:

132
1
14
2
5
3814986502092304

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4165

题目解析:这题是卡特兰数列。具体的看百度百科里面有解释。

                    题意:在一个瓶子里有N片药,每次吃半片,从瓶子里可能拿出整片,也可能拿出半片,如果拿出整片,记为W,半片记为H。问有多少种排列。

用两个状态写的时候这个题就很水了

 Pills容易的出状态方程:dp[i][j]=dp[i-1][j]+dp[i][j-1];

 

代码:

#include<cstdio>
#include<cmath>
#include<stack>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define clr(x) memset(x,0,sizeof(x))
long long dp[31][31];
bool inti(){
	clr(dp);
	for(int i=0;i<=30;i++){
		dp[i][0]=1;
	}
	for(int i=1;i<=30;i++){
		for(int j=1;j<=i;j++){
			dp[i][j]=dp[i-1][j]+dp[i][j-1];
		}
	}
	return true;
}
int main(){
	inti();
	int i,j,k,m,n;
	while(cin>>n&&n){
		cout<<dp[n][n]<<endl;
	}
	return 0;
}

 

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/yujuan_mao/article/details/8219125