P1044. 模板题_栈

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 769 阅读时长 ≈ 3 分钟

考点

  • 卡特兰数
  • 线性动态规划

题解

见思路

思路

卡特兰数

卡特兰数本身并不难理解，可以直接看这篇链接进行学习

这里提醒一下，在《深基》与《算法导论》中非法序列的个数为\(C_{2n}^{n-1}\)，在上面的链接中则是\(C_{2n}^{n+1}\)；但结果是一样的，只是角度不同

因为组合数本来就有这个性质： \[ C_{n}^{m}=C_{n}^{n-m} \] 故而本题可以直接按照卡特兰数的通项输出即可，不再赘述

递推

思路来源于kkksc03

假设i个元素一共有h[i]种出栈方式，那么要求的就是n个元素的出栈方式，即h[n]

n个元素下标为从1到n，每个元素都有可能是最后一个出栈的，即输出序列的最后一位

假设第k个数是最后一个出栈的，情况会是这样：

  1. 前面有k-1个数先入栈，然后出栈，即h[k-1]

  2. 第k个数入栈

  3. n-k个数入栈，然后出栈，即h[n-k]

所以当第k个数是最后一个出栈时，情况共有h[k-1] * h[n-k]种

那么就能得到递推式： \[ h\left( n \right) =h\left( 0 \right) \times h\left( n-1 \right) +h\left( 1 \right) \times h\left( n-2 \right) +...+h\left( n-1 \right) \times h\left( 0 \right) \]

\[ h\left( 0 \right) =h\left( 1 \right) =1 \]

这样就能写出极简代码了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    int n, h[20] = {1, 1};
    cin >> n;
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j < i; ++j)
            h[i] += h[j] * h[i - j - 1];
    }
    cout << h[n];
    return 0;
}

线性动态规划 记忆化搜索

以输出序列的元素个数qe，栈的元素个数st为状态分析对象，建立二维数组mem[qe][st]

根据栈的性质，要么从栈顶弹出一个元素给输出序列，要么就继续入栈新元素不弹出；易得状态转移方程如下： \[ \underset{\text{栈顶弹出给输出序列}}{\underbrace{mem\left[ qe-1 \right] \left[ st+1 \right] }}+\underset{\text{入栈新元素不弹出}}{\underbrace{mem\left[ qe \right] \left[ st-1 \right] }}\rightarrow mem\left[ qe \right] \left[ st \right] \] 那么临界值呢？很显然，当输出序列qe为0的时候不可再分，此时令mem[qe][st] = 1；如果越界的话令mem[qe][st] = 0即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

ll mem[20][20];

int dfs(int qe, int st)
{
    if (mem[qe][st])
        return mem[qe][st];
    if (qe < 0 || qe > n || st < 0 || st > n)
        return mem[qe][st] = 0;
    if (qe == 0)
        return mem[qe][st] = 1;
    return mem[qe][st] = dfs(qe - 1, st + 1) + dfs(qe, st - 1);
}

int main()
{
    cin >> n;
    cout << dfs(n, 0);
}

线性动态规划 递推

将上面的递归改成迭代即可，不再赘述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;

ll dp[20][20];

int main()
{
    cin >> n;
    for (int st = 0; st <= n; ++st)
        dp[0][st] = 1;
    for (int qe = 1; qe <= n; ++qe)
    {
        for (int st = 0; st <= n; ++st)
        {
            dp[qe][st] = dp[qe - 1][st + 1] + dp[qe][st - 1];
        }
    }
    cout << dp[n][0];
}