题意:
给出一个长度为 $n - 1 的字符串, s_i 为'I', 'D', '?'$
$'I'表示 a_i <a_{i + 1}$
$'D'表示 a_i> a_{i + 1}$
$'?' 表示 a_i 和 a_{i + 1} 的大小关系任意 $
思路:
$dp[i][j] 表示考虑到第 i 位, 当前位的数字位 j 的方案数 $
$s[i - 1] == '?' 那么 dp[i][j] = \sum_{k = 1}^{i - 1} dp[i - 1][k]$
$s[i - 1] == 'I' 那么 dp[i][j] = \sum_{k = 1}^{j - 1} dp[i - 1][k]$
$s[i - 1] == 'D' 那么 dp[i][j] = \sum_{k = j}^{k = i - 1} dp[i - 1][k]$
$ 第三个转移可以这样考虑, 比如说之前有一个排列 {1, 3, 2} 那么我当前后面插入一位 2$
$ 我们把 {1, 3, 2} 中 >= 2 的数字都加 1 再加入 2 就变成 {1, 4, 3, 2}$
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define N 1010
- const ll MOD = (ll)1e9 + 7;
- char s[N];
- ll f[N][N];
- int main()
- {
- while (scanf("%s", s + 2) != EOF)
- {
- f[1][1] = 1;
- int n = strlen(s + 2) + 1;
- for (int i = 2; i <= n; ++i)
- {
- if (s[i] == 'I')
- {
- for (int j = 1; j <= i; ++j)
- f[i][j] = (f[i][j - 1] + f[i - 1][j - 1]) % MOD;
- }
- else if (s[i] == 'D')
- {
- for (int j = i; j>= 1; --j)
- f[i][j] = (f[i][j + 1] + f[i - 1][j]) % MOD;
- }
- else
- {
- ll sum = 0;
- for (int j = 1; j < i; ++j)
- sum = (sum + f[i - 1][j]) % MOD;
- for (int j = 1; j <= i; ++j)
- f[i][j] = sum;
- }
- }
- ll res = 0;
- for (int i = 1; i <= n; ++i) res = (res + f[n][i]) % MOD;
- printf("%lld\n", res);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2931790.html