Niuke / Luogu - [noip2003 popularization group] stack

Background

Stack is the classic data structure in computer , To put it simply , A stack is a linear table that is limited to insert and delete operations at one end .

The stack has two most important operations , namely pop（ Pop an element from the top of the stack ） and push（ Stack an element ）.

The importance of stacks is self-evident , Any course on data structure will introduce stacks . Ning Ning was reviewing the basic concept of stack , I think of a problem that is not mentioned in the book , And he can't give the answer himself , So I need your help .

Title Description

Ning Ning is thinking about such a problem ： A sequence of operands ,1,2,\ldots ,n1,2,…,n（ Shown here 1 To 3 The situation of ）, Stack A The depth of is greater than  nn.

Now you can do two things ,

1. Count a number , Move from the header of the sequence of operands to the header of the stack （ Corresponding to the data structure stack push operation ）
2. Count a number , Move from the head of the stack to the end of the output sequence （ Corresponding to the data structure stack pop operation ）

Use these two operations , From a sequence of operands, we can get a series of output sequences , The figure below shows  1 2 3  Generating sequences  2 3 1  The process of .

（ The original state is shown in the figure above ）

Your program will respond to a given  n, Computes and outputs a sequence of operands 1,2,…,n  The total number of possible output sequences after operation .

Input format

The input file contains only one integer n（1≤n≤18）.

Output format

The output file has only one line , That is, the total number of possible output sequences .

I/o sample

Input #1

3

Output #1

5

explain / Tips

【 Title source 】

NOIP 2003 Third question of popularization group

Answer key ：

So here I'm going to use theta dp The main yes Other methods will not , There are two situations ： There is a number in the stack and there is no number in the stack , This procedure is very easy 了 .

Judgement procedure ：

if(i>=1)// If there are a few in the station, the number that is not in the stack -1, Number in stack +1
    dp[i][j]=dp[i-1][j]+dp[i+1][j-1];
if(i==0)// There are no numbers in the station , Can only enter the stack 
    dp[i][j]=dp[i+1][j-1];

Program ：

#include<bits/stdc++.h>
using namespace std;
int n,dp[20][20];
int main(){
    cin>>n;
    for(int i=0;i<=n;i++)
       dp[i][0]=1;// Set boundary  
    for(int j=1;j<=n;j++)// Refers to the number of numbers that have not been stacked 
        for(int i=0;i<=n;i++){// Refers to the number of numbers in the stack  
            if(i>=1)// If there are a few in the station, the number that is not in the stack -1, Number in stack +1
        		dp[i][j]=dp[i-1][j]+dp[i+1][j-1];
            if(i==0)// There are no numbers in the station , Can only enter the stack 
            	dp[i][j]=dp[i+1][j-1];
        }
    cout<<dp[0][n];
    return 0;
}