Loj 2273 数列

Posted on | Views:

dp 计数.

不难发现,合法的选择区间会在选一个数之后不断收缩,将它作为状态记录下来 dp 即可.

设 $dp(i,l,r,k)$ 表示考虑了前 $i$ 个数,下个数合法的选择区间为 $[l,r]$ , 最后一个数的值为 $k$ 的方案数.

转移时,对于 $[l,l],[l+1,k-1],[k,k],[k+1,r-1],[r,r]$ 这几段分别转移,每一段内转移到新的 $l,r$ 是一样的.

于是修改差分就可以完成 $O(1)$ 转移,注意处理 $l,r$ 不存在等特殊情况,时间复杂度 $O(n\cdot r^3)$ .

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 998244353;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
const int N = 150 + 10;
int n, m = 0, dp[2][N][N][N], t[N];
void trans(int id, int l, int r, int L, int R, int v)
{
	if (L > R)
		return;
	inc(dp[id ^ 1][l][r][L], v);
	inc(dp[id ^ 1][l][r][R + 1], P - v);
}
int main()
{
	n = read();
	for (int i = 1; i <= n; ++i)
		m = max(m, t[i] = read());
	int id = 0, bound = t[1], L, R;
	dp[id][0][m + 1][1] = 1, dp[id][0][m + 1][bound + 1] = P - 1;
	for (int i = 2; i <= n; ++i)
	{
		for (int l = 0; l <= m + 1; ++l)
			for (int r = l; r <= m + 1; ++r)
				for (int k = l; k <= r; ++k)
					inc(dp[id][l][r][k], dp[id][l][r][k - 1]);
		bound = t[i];
		for (int l = 0; l <= m + 1; ++l)
			for (int r = l; r <= m + 1; ++r)
				for (int k = l; k <= r; ++k)
					dp[id ^ 1][l][r][k] = 0;
		for (int l = 0; l <= m + 1; ++l)
			for (int r = l; r <= m + 1; ++r)
				for (int k = l; k <= r; ++k) if (dp[id][l][r][k])
				{
					L = max(l, 1), R = min(l, bound);
					trans(id, l, l, L, R, dp[id][l][r][k]);
					L = max(l + 1, 1), R = min(k - 1, bound);
					trans(id, l, k, L, R, dp[id][l][r][k]);
					if (k > l)
					{
						L = max(k, 1), R = min(k, bound);
						trans(id, k, k, L, R, dp[id][l][r][k]);
					}
					L = max(k + 1, 1), R = min(r - 1, bound);
					trans(id, k, r, L, R, dp[id][l][r][k]);
					if (r > k)
					{
						L = max(r, 1), R = min(r, bound);
						trans(id, r, r, L, R, dp[id][l][r][k]);
					}
				}
		id ^= 1;
	}
	int ans = 0;
	for (int l = 0; l <= m + 1; ++l)
		for (int r = l; r <= m + 1; ++r)
			for (int k = l; k <= r; ++k)
			{
				inc(dp[id][l][r][k], dp[id][l][r][k - 1]);
				inc(ans, dp[id][l][r][k]);
			}
	write(ans, '\n');
	return 0;
}