Codeforces 1000D(DP+组合数)

Codeforces 1000D
题意:定义一个序列是“好的”:第一个数字$a_0$为序列长度$+1$。定义一个序列的子序列是“好的”:这个子序列能分割成几个“好的”序列。给出一个序列,求“好的”子序列的数目。

一开始我想把所有这种序列全部求出来然后组合。。具体就是每个点往后面找,用组合数。然后再合并。但是行不通。。
这题直接从后面往前面 DP 即可。设$dp(i)$为$[i, n]$“好的”子序列个数。我们这样定下来了左端点,再枚举一个右端点$j$,使当前所有“好的”序列最后一个是$j$,那么和$j$后面已经算完的 DP 值乘起来即可。

可能直接初值$dp(n+1)=1$,转移$dp(i)=dp(j) \times C(j-i-1,a_i)$更好?

知识点:
1、DP 从后往前

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 1000 + 5;
const LL MO = 998244353;
int n, a[MAXN];
LL c[MAXN][MAXN], dp[MAXN], suf[MAXN];
void clean() {
ms(dp, 0), ms(suf, 0);
}
int solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
clean();
for (int i = 0; i <= n; ++i) c[i][0] = c[i][i] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MO;
// for (int i = 0; i <= n; ++i, cerr << endl)
// for (int j = 0; j <= i; ++j) cerr << c[i][j] << " ";
LL ans = 0ll;
for (int i = n; i; --i) {
if (a[i] > 0 && i + a[i] <= n)
for (int j = i + a[i]; j <= n; ++j) {
dp[i] = (dp[i] + (c[j - i - 1][a[i] - 1] * (1ll + suf[j + 1])) % MO) % MO;
}
suf[i] = (suf[i + 1] + dp[i]) % MO;
}
cout << suf[1];
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------