原序列为
a
a
a
，答案序列为
p
p
p
。
令
f
[
i
]
[
j
]
f[i][j]
f
[
i
]
[
j
]
表示构造了结果序列的前
i
i
i
位，
p
[
i
]
=
a
[
j
]
p[i] = a[j]
p
[
i
]
=
a
[
j
]
的方案数。
[
L
[
i
]
,
R
[
i
]
]
[L[i], R[i]]
[
L
[
i
]
,
R
[
i
]
]
是满足
L
[
i
]
≤
i
≤
R
[
i
]
,
∀
j
∈
[
L
[
i
]
,
R
[
i
]
]
,
a
[
j
]
≥
a
[
i
]
L[i] \leq i \leq R[i], \forall j \in [L[i], R[i]], a[j] \geq a[i]
L
[
i
]
≤
i
≤
R
[
i
]
,
∀
j
∈
[
L
[
i
]
,
R
[
i
]
]
,
a
[
j
]
≥
a
[
i
]
的最大区间。
f
[
i
]
[
j
]
=
[
L
[
j
]
≤
i
≤
R
[
j
]
]
∗
∑
f
[
i
−
1
]
[
k
]
(
k
≤
j
)
f[i][j] = [L[j] \leq i \leq R[j]] * \sum f[i – 1][k] (k \leq j)
f
[
i
]
[
j
]
=
[
L
[
j
]
≤
i
≤
R
[
j
]
]
∗
∑
f
[
i
−
1
]
[
k
]
(
k
≤
j
)
状态转移分析：
subtask 1
首先解释
k
≤
j
k \leq j
k
≤
j
为什么
k
>
j
k > j
k
>
j
没有贡献呢？
-
condition 1
k>
j
≥
i
−
1
k > j \geq i – 1
k
>
j
≥
i
−
1
如果
k≥
j
k \geq j
k
≥
j
， 并且
a[
k
]
a[k]
a
[
k
]
将
p[
i
−
1
]
p[i – 1]
p
[
i
−
1
]
修改了，那么说明
∀j
∈
[
i
−
1
,
k
]
,
p
[
j
]
←
a
[
k
]
\forall j \in [i – 1, k], p[j] \leftarrow a[k]
∀
j
∈
[
i
−
1
,
k
]
,
p
[
j
]
←
a
[
k
]
，那么操作了
a[
k
]
a[k]
a
[
k
]
后
p[
j
]
p[j]
p
[
j
]
肯定是
a[
k
]
a[k]
a
[
k
]
，这时候再考虑
p[
i
]
←
a
[
j
]
p[i] \leftarrow a[j]
p
[
i
]
←
a
[
j
]
就不对了。 -
condition 2
k≥
i
−
1
>
j
k \geq i – 1 > j
k
≥
i
−
1
>
j
这种情况下，如果
p[
i
−
1
]
←
a
[
k
]
p[i – 1] \leftarrow a[k]
p
[
i
−
1
]
←
a
[
k
]
，
p[
i
]
←
a
[
j
]
p[i] \leftarrow a[j]
p
[
i
]
←
a
[
j
]
，那么修改后的序列和
dp
[
i
−
1
]
[
j
]
dp[i – 1][j]
d
p
[
i
−
1
]
[
j
]
所提供的序列重复了，所以只算
dp
[
i
−
1
]
[
j
]
dp[i – 1][j]
d
p
[
i
−
1
]
[
j
]
就好了。 -
condition 3
i−
1
>
k
>
j
i – 1 > k > j
i
−
1
>
k
>
j
和
condition 2
一个道理。
subtask 2
再来解释一下方程
这个转移是怎么一个过程呢：
∑
f
[
i
−
1
]
[
k
]
,
k
≤
j
\sum f[i – 1][k], k \leq j
∑
f
[
i
−
1
]
[
k
]
,
k
≤
j
相当于我们用各种方法把
[
1
,
i
−
1
]
[1, i – 1]
[
1
,
i
−
1
]
搞成各不相同的样子，然后我们再
p
[
i
]
←
a
[
j
]
p[i] \leftarrow a[j]
p
[
i
]
←
a
[
j
]
。
再来证明一下正确性
不重：
由于状态定义：首先
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
k
]
(
j
≠
k
)
dp[i – 1][j],dp[i – 1][k] (j \neq k)
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
−
1
]
[
k
]
(
j
=
k
)
中包含的答案状态一定不同（因为
p
j
[
i
−
1
]
=
a
[
j
]
,
p
k
[
i
−
1
]
=
a
[
k
]
p_j[i – 1] = a[j], p_k[i – 1] = a[k]
p
j
[
i
−
1
]
=
a
[
j
]
,
p
k
[
i
−
1
]
=
a
[
k
]
）；又由于状态定义，
d
p
[
i
−
1
]
[
j
]
dp[i – 1][j]
d
p
[
i
−
1
]
[
j
]
内部的答案状态也一定不同。
不漏：
如果当前
p
[
i
]
=
a
[
j
]
p[i] = a[j]
p
[
i
]
=
a
[
j
]
， 那么
p
[
i
−
1
]
p[i – 1]
p
[
i
−
1
]
的值无非就只有
a
[
1
a[1
a
[
1
~
j
]
j]
j
]
。其余情况根据
subtask 1
，他们一定不满足要求。
参考代码：
#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define db double
#define LL long long
#define PII pair <int, int>
#define MP(x,y) make_pair (x, y)
#define rep(i,j,k) for (int i = (j); i <= (k); i++)
#define per(i,j,k) for (int i = (j); i >= (k); i--)
template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
template <typename T>
bool read (T &x) {
x = 0; T f = 1;
char ch = getchar ();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar ();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar ();
}
x *= f;
return 1;
}
template <typename T>
void write (T x) {
if (x < 0) {
putchar ('-');
x = -x;
}
if (x < 10) {
putchar (x + '0');
return;
}
write (x / 10);
putchar (x % 10 + '0');
}
template <typename T>
void print (T x, char ch) {
write (x); putchar (ch);
}
const int Maxn = 5 * 1e3;
const LL Mod = 1e9 + 7;
int n;
int a[Maxn + 5], l[Maxn + 5], r[Maxn + 5];
LL dp[2][Maxn + 5], pre[Maxn + 5];
#define add(x,y) ((x += y) >= Mod && (x -= Mod))
signed main () {
// freopen ("C:\\Users\\Administrator\\Desktop\\vscode\\1.in", "r", stdin);
// freopen ("C:\\Users\\Administrator\\Desktop\\vscode\\1.out", "w", stdout);
// freopen ("C.in", "r", stdin);
// freopen ("C.out", "w", stdout);
read (n);
for (int i = 1; i <= n; i++)
read (a[i]);
a[0] = -1; a[n + 1] = -1;
rep (i, 1, n) {
per (j, i, 0)
if (a[j] < a[i])
{ l[i] = j + 1; break; }
rep (j, i, n + 1)
if (a[j] < a[i])
{ r[i] = j - 1; break; }
}
rep (j, 1, n) {
if (l[j] <= 1 && 1 <= r[j])
dp[1][j] = 1;
else
dp[1][j] = 0;
}
bool f = 0;
rep (i, 2, n) {
memset (pre, 0, sizeof pre);
rep (j, 1, n) {
pre[j] = pre[j - 1];
add (pre[j], dp[f ^ 1][j]);
}
rep (j, 1, n) {
if (l[j] <= i && i <= r[j])
dp[f][j] = pre[j];
else
dp[f][j] = 0;
}
// rep (j, 1, n) {
// printf ("dp[%d][%d] = %lld\n", i, j, dp[f][j]);
// }
f ^= 1;
}
LL res = 0;
rep (i, 1, n)
add (res, dp[n & 1][i]);
write (res);
return 0;
}