题目描述

样例

Input

19198210

Output

算法1

(类似状态机的dp) $O (n)$

这题其实不难，仔细思考片刻这题其实就可以把他分成多个部分：

将题目中的2 3 4 5 6 7 部分我们分为2 3 4 5 6 7阶段

上升部分：就是 $a_{1}$ < $a_{2}$ ,以及 $a_{3}$ < $a_{4}$ 两个部分，也就是题中2和4 下降部分：也就是其他部分，题中3 5 6 7 四个部分分成这两个部分以后，首先我们看看2阶段的状态转移：

若只看1，2阶段，我们的任务便变成了，寻找长度为2的上升子序列若当前想要得到以第 i 个字符结尾的长度为2的上升子序列

那么我们要的是前 i - 1 个字符中所有小于第 i 个字符和当我们求出第2阶段值后，类似的第3阶段我们的任务是：寻找长度为3并先上升后下降的子序列：我们已经求出上升并长度为2的子序列所以我们接下来需要,求得是以第i个字符结尾长度为3的先上升再下降的子序列:

我们要的是前i - 1个字符为结尾的长度为2的上升序列中结尾字符大于第 i 个字符的和以此类推第 4 5 6 7 阶段便是从前一个阶段往后加一个字符

C++ 代码

/*

							记得取模！！！！！！！！！！！！！！！！！！！！！！！！！！


*/
#include "bits/stdc++.h"

using namespace std;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
ll num[10];// 用来记录大小为 0 1 2 ...... 8 9 结尾的前一个阶段的前缀和
ll dp[10][N];

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
        dp[1][i] = 1;
    for (int i = 2; i <= 7; i++) {
        memset(num, 0, sizeof num);
        if (i == 2 || i == 4) {
            for (int j = 0; j < s.size(); j++) {
                ll x = s[j] - '0', res = 0;
                for (int k = 0; k < x; k++)
                    res = (num[k] + res) % mod;
                dp[i][j] = res;
                num[x] = (dp[i - 1][j] + num[x]) % mod;
            }
        } else {
            for (int j = 0; j < s.size(); j++) {
                ll x = s[j] - '0', res = 0;
                for (int k = 9; k > x; k--)
                    res = (num[k] + res) % mod;
                dp[i][j] = res;
                num[x] = (dp[i - 1][j] + num[x]) % mod;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < s.size(); i++)
        ans = (dp[7][i] + ans) % mod;
    cout << ans << endl;
}

题解 | #1919810#

题目描述

样例

Input

Output

算法1

(类似状态机的dp) $O (n)$

C++ 代码

总结

本题所用姿势点

遇到的bugs

题解 | #1919810#

题目描述

样例

Input

Output

算法1

(类似状态机的dp) O(n)O(n)O(n)

C++ 代码

总结

本题所用姿势点

遇到的bugs

(类似状态机的dp) $O (n)$