AtCoder Grand Contest 058

B Adjacent Chmax

题意: 给定一个[1…n]的一个排列，有一种操作将$(p_i,p_{i+1})$ 替换为 $(max(p_i,p_{i+1}),max(p_i,p_{i+1}))$,可以进行0次或者无数次
思路：首先想到支配区间，如果$p_i$ 是$(L,R)$ 区间的最大值，那么$(L,R)$就是$p_i$的支配区间，他可以把支配区间中所有数变成$p_i$,于是有状态$dp[i][j]$ 代表发生替换的数为$(p_1,p_{i-1})$,当前替换的数为$p_i$, $[p_j,p_i]$ 都变成了$p_i$,$[1,N]$的最终形式有多少种？
$$dp[i][j]=dp[i-1][j]+dp[i][j-1]j\in (L,R]$$
去除第一维
$$dp[j]=dp[j]+dp[j-1]$$

#include
using namespace std;

const int maxn = 5000+10;
const int mod = 998244353; 
int A[maxn];
int dp[maxn];
int main(void) {
	int N;
	cin>>N;
	for(int i = 1;i <= N; ++i) {
		cin>>A[i]; 
	}
	dp[0] = 1;
	for(int i = 1;i <= N; ++i) {
		int l = i-1,r = i+1;
		while(l > 0 && A[l] < A[i]) l--;
		while(r <= N && A[r] < A[i]) r++;
		for(int j = l+1;j < r; ++j) (dp[j]+=dp[j-1])%=mod;
	}


	cout<<dp[N]<<endl;
	return 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