2015
05-23

# 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

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

容易的出状态方程：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;
}