题目描述
https://codeforces.com/gym/103102/problem/F
简要题意：给定一个长度为 $n$ 的排列 $p_i$，现在你可以若干次操作，每次操作选定一个区间 $[l,r]$，将区间 $[l,r]$ 内的数都变成 $[l,r]$ 的最小值，求可能会有多少种序列
$n\le 3000$
Solution
我们令 $l_i$ 表示 $p_i$ 左边第一个比 $p_i$ 小的位置，$r_i$ 表示 $p_i$ 右边第一个比 $p_i$ 小的位置，容易在最终序列中得到 $p_i$ 能够控制的区间一定是 $[l_i+1,r_i-1]$ 的一个子区间
那么我们考虑 $dp$，令 $f_{i,j}$ 表示前 $i$ 个 $p$，控制了 $[1,j]$ 这个区间，容易得到转移如下：
1
2
3
4
5
| for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= n; ++j) f[i][j] = f[i - 1][j];
for (int j = l[i] + 1; j <= r[i] - 1; ++j)
for (int k = l[i]; k < j; ++k) f[i][j] = (f[i][j] + f[i - 1][k]) % p;
}
|
注意到 $k$ 的枚举是一个区间，我们求一个前缀和即可
时间复杂度 $O(n^2)$
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
| #include <iostream>
#include <stack>
#define maxn 3010
using namespace std;
const int p = 1000000007;
int n, a[maxn], l[maxn], r[maxn];
int f[maxn][maxn], s[maxn];
inline int get(int l, int r) {
if (l == 0) return s[r];
return (s[r] - s[l - 1] + p) % p;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
stack<int> S; S.push(a[0]); a[0] = a[n + 1] = 0;
for (int i = 1; i <= n + 1; ++i) {
while (!S.empty() && a[i] < a[S.top()]) r[S.top()] = i, S.pop();
l[i] = S.top(); S.push(i);
} f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
s[0] = 1; for (int j = 1; j <= n; ++j) s[j] = (s[j - 1] + f[i - 1][j]) % p;
for (int j = 0; j <= n; ++j) f[i][j] = f[i - 1][j];
for (int j = l[i] + 1; j <= r[i] - 1; ++j) f[i][j] = (f[i][j] + get(l[i], j - 1)) % p;
}
cout << f[n][n] << "\n";
return 0;
}
|