自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 23:04:04，当前版本为作者最后更新于2024-09-22 16:29:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先对 $a$ 离散化。思路当然是 $dp_{i,j}$ 算以 $i$ 结尾最高峰为 $j$ 的子序列有多少个。但是有些问题：

• 每个山峰至少要有一个上坡。
• 若出现了 V 字形的峡谷，那么同一个子序列会对应两种划分成山峦的方案。

解决方法是添加一个起始点来区分。设 $dp_{i,j,0/1/2/3}$ 表示以 $i$ 结尾，最高峰为 $j$，当前刚开始上坡/正在上坡/刚开始下坡/正在下坡的方案数，那么答案为 $\sum dp_{i,j,2}+dp_{i,j,3}$。考虑转移：

• $0$ 可以在 $2$ 后面任意接，也可以在 $3$ 后面的下方接。
• $1$ 可以在 $0/1$ 后面的上方接。
• $2$ 可以在 $1$ 后面的下方接，同时更新最高峰。
• $3$ 可以在 $2/3$ 后面的下方接。

转移需要枚举上一个，复杂度为 $O(n)$，总时间复杂度为 $O(n^3)$。发现转移时对于同个 $j$ 求的是所有 $<a_i$ 或 $>a_i$ 的位置之和，可以用树状数组优化到 $O(n^2\log n)$。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e2 + 10;
const int mod = 998244353;

inline void add(int &x, int y) { x += y, x < mod || (x -= mod); }

int n, m, a[MAXN], b[MAXN], dp[MAXN][MAXN][4], ans;

// dp_i,j,0:新开一个向上单点（只能从下坡转移） 
// dp_i,j,1:上坡
// dp_i,j,2:新开一个向下单点 
// dp_i,j,3:下坡 

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
	sort(b + 1, b + n + 1), m = unique(b + 1, b + n + 1) - b - 1;
	for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
	for (int i = 1; i <= n; i++) {
		dp[i][0][0] = 1;
		for (int j = 1; j < i; j++) {
			for (int k = 0; k <= m; k++) {
				add(dp[i][k][0], dp[j][k][2]);
				if (a[i] <= a[j]) add(dp[i][k][0], dp[j][k][3]);
			}
		}
		for (int j = 1; j < i; j++) {
			if (a[j] >= a[i]) continue;
			for (int k = 0; k <= m; k++) {
				add(dp[i][k][1], dp[j][k][0]);
				add(dp[i][k][1], dp[j][k][1]);
			}
		}
		for (int j = 1; j < i; j++) {
			if (a[j] <= a[i]) continue;
			for (int k = 0; k < a[j]; k++) {
				add(dp[i][a[j]][2], dp[j][k][1]);
			}
		}
		for (int j = 1; j < i; j++) {
			if (a[j] <= a[i]) continue;
			for (int k = 0; k <= m; k++) {
				add(dp[i][k][3], dp[j][k][2]);
				add(dp[i][k][3], dp[j][k][3]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			add(ans, dp[i][j][2]);
			add(ans, dp[i][j][3]);
		}
	}
	printf("%d", ans);
}