---

题目重述

构造长度为 $n$ 的序列 $A$，满足：

1. $1 \le A_i \le r_i$
2. 对于 $i \ge 3$，设：
   • $R$ = 前 $i-2$ 个数中 $\ge A_{i-1}$ 的最小值（不存在则为 $+\infty$）
   • $L$ = 前 $i-2$ 个数中 $\le A_{i-1}$ 的最大值（不存在则为 $-\infty$） 要求 $L \le A_i \le R$

求不同的序列个数，对 $998244353$ 取模。

---

深入理解限制条件

这个条件实际上是在维护一个 动态的有序集合：

• 当我们已经选择了 $A_1, A_2, \dots, A_{i-1}$ 时，这些数字形成了一个集合
• 对于 $A_{i-1}$，在这个集合中它有 前驱（比它小的最大数）和 后继（比它大的最小数）
• $A_i$ 必须落在 $[前驱, 后继]$ 这个区间内

特殊情况：

• 如果 $A_{i-1}$ 是当前最小的，则前驱 = $-\infty$
• 如果 $A_{i-1}$ 是当前最大的，则后继 = $+\infty$

---

关键性质分析

1. 区间单调性

随着序列的增长，$A_{i-1}$ 对应的区间 $[L, R]$ 会 越来越窄，因为集合中的数字越来越多，前驱和后继会越来越接近 $A_{i-1}$。

2. 状态可压缩性

我们不需要记住所有之前选择的数字，只需要知道：

• 当前 $A_{i-1}$ 的值
• 它的前驱 $L$
• 它的后继 $R$

因为这三个值已经包含了确定 $A_i$ 取值范围的全部信息。

---

详细状态设计

令：

dp[i][last][L][R] = 方案数

其中：

• $i$: 当前要填第 $i$ 个位置（从 1 开始）
• $last$: $A_{i-1}$ 的值
• $L$: 前驱（$-\infty$ 或某个具体值）
• $R$: 后继（$+\infty$ 或某个具体值）

状态含义：在已经确定了前 $i-1$ 个数，且满足：

• $A_{i-1} = last$
• 在 $A_1 \dots A_{i-2}$ 中，小于等于 $last$ 的最大值是 $L$
• 在 $A_1 \dots A_{i-2}$ 中，大于等于 $last$ 的最小值是 $R$

的情况下，填写剩余位置的方案数。

---

状态转移分析

从状态 $(i, last, L, R)$ 出发：

枚举 $A_i = x$，需要满足：

1. $1 \le x \le r_i$（值域限制）
2. $L \le x \le R$（区间限制）

然后根据 $x$ 与 $last$ 的关系，更新前驱后继：

情况 1: $x < last$

A_{i-1} = last
A_i = x (< last)

在集合 $\{A_1, \dots, A_{i-1}\}$ 中：

• $x$ 的前驱仍然是 $L$（不变）
• $x$ 的后继变成 $last$（因为 $last > x$ 且是最接近的）

新状态：$(i+1, x, L, last)$

情况 2: $x > last$

A_{i-1} = last  
A_i = x (> last)

在集合 $\{A_1, \dots, A_{i-1}\}$ 中：

• $x$ 的前驱变成 $last$（因为 $last < x$ 且是最接近的）
• $x$ 的后继仍然是 $R$（不变）

新状态：$(i+1, x, last, R)$

情况 3: $x = last$

A_{i-1} = last
A_i = last

前驱后继不变（因为集合中已经有 $last$）

新状态：$(i+1, last, L, R)$

---

边界情况处理

初始状态 ($i = 2$)

• 只有 $A_1$ 被选择
• $last = A_1$（枚举 $1 \dots r_1$）
• $L = -\infty$（前面没有比 $A_1$ 小的数）
• $R = +\infty$（前面没有比 $A_1$ 大的数）

终止状态 ($i = n+1$)

所有位置填完，返回 1。

---

离散化实现

由于 $L, R$ 可能是 $\pm\infty$，需要映射到数组下标：

const int INF = 200;    // 表示 +∞
const int NINF = 0;     // 表示 -∞  
const int MAXV = 201;   // 值域上限

int get_idx(int x) {
    if (x == NINF) return 0;
    if (x == INF) return MAXV - 1;
    return x;  // 实际值从 1 到 150
}

---

完整代码（带详细注释）

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int INF = 200;      // 表示 +∞
const int NINF = 0;       // 表示 -∞
const int MAXV = 201;     // 值域大小 (0: -∞, 1..150: 实际值, 200: +∞)
const int MAXN = 155;

int n;
vector<int> r;
int dp[MAXN][MAXV][MAXV][MAXV];  // dp[pos][last][L][R]

// 将值映射到数组下标
int get_idx(int x) {
    if (x == NINF) return 0;
    if (x == INF) return MAXV - 1;
    return x;
}

int dfs(int pos, int last, int L, int R) {
    if (pos == n) return 1;  // 所有位置填完
    
    int &res = dp[pos][last][get_idx(L)][get_idx(R)];
    if (res != -1) return res;
    
    res = 0;
    int max_val = r[pos];  // 当前位的上限
    
    for (int x = 1; x <= max_val; x++) {
        // 检查是否在 [L, R] 范围内
        if (L != NINF && x < L) continue;
        if (R != INF && x > R) continue;
        
        int new_L = L, new_R = R;
        
        if (x < last) {
            // x 比 last 小，last 成为 x 的后继
            new_R = last;
        } else if (x > last) {
            // x 比 last 大，last 成为 x 的前驱  
            new_L = last;
        }
        // x == last 时前驱后继不变
        
        res = (res + dfs(pos + 1, x, new_L, new_R)) % MOD;
    }
    
    return res;
}

int main() {
    cin >> n;
    r.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> r[i];
    }
    
    memset(dp, -1, sizeof(dp));
    
    int ans = 0;
    // 枚举第一个数字 A1
    for (int a1 = 1; a1 <= r[0]; a1++) {
        // 初始状态：pos=1, last=a1, L=-∞, R=+∞
        // 注意：这里 pos=1 表示接下来要填第2个位置
        ans = (ans + dfs(1, a1, NINF, INF)) % MOD;
    }
    
    cout << ans << endl;
    return 0;
}

---

复杂度优化讨论

当前复杂度

• 状态数：$O(n \cdot M^3)$，$M \approx 150$
• 转移：$O(M)$
• 总复杂度：$O(n \cdot M^4) \approx 150 \cdot 150^4 \approx 7.6 \times 10^9$（理论上不可行）

实际优化方法

1. 值域离散化：$L$ 和 $R$ 只能是之前出现过的值或 $\pm\infty$，所以实际状态数远小于 $M^3$

2. 状态剪枝：很多 $(L, R)$ 组合是无效的（$L > R$ 或区间为空）

3. 迭代DP：改用递推式，按位置顺序计算，避免递归开销

4. 滚动数组：只需要保存上一层的状态

---

算法总结

这道题的核心在于 识别出影响后续决策的关键信息（前驱后继），从而将指数级的状态空间压缩到多项式级别。这是动态规划中 状态设计优化 的典型例子。

通过将复杂的过程限制抽象为简单的区间约束，我们能够用 $O(n \cdot M^3)$ 的状态数来解决原本看似需要 $O(M^n)$ 的问题。