ACM 训练日志记录 · 思考 · 成长 提交 / 修改记录
王梓豪 / 题目列表训练档案
导出

P1044 栈

来源:洛谷 ★ 1000

本题活力0.26按难度、完成结果与训练证据估算

算法如山行则将至

题目描述

给定操作数序列1,2,…,n和一个深度大于n的栈,通过push和pop操作生成输出序列,求可能的输出序列总数。

代码

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <unordered_set>
#include <map>
#include <algorithm>
#include<unordered_map>
#include <cstdio>
#include <string>
#include <set>
#include <queue>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    n++;
    vector<vector<int>> a(n,vector<int>(n));
    for(int i=0;i<n;i++)
    {
        a[0][i]=1;
    }
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<n-i;j++)
        {
            if(j>0)a[i][j]=a[i][j-1]+a[i-1][j+1];
            else if(j==0)a[i][j]=a[i-1][j+1];
        }
    }
    cout<<a[n-1][0]<<endl;
}