题解 | #学姐的编码1.0#

题解 | #学姐的编码1.0#
说实话看到前半段的时候还以为是数位dp，差点把板子都给敲了，看到后半段才发现根本不是。。。本来是没什么灵感的，看到数据范围是1e6，猜测是线性递推的做法，于是就蒙了一下做法。。。再次给出及其简短的代码

#include<bits/stdc++.h>
using namespace std;
char s[1000010];
int dp[20],t, ans = 0;
int main(){
    cin >> s;
    int len = strlen(s);
    for(int i = 0; i < len; i++)
    {
        if(s[i] >= '0' && s[i] <= '9')  t = s[i] - '0';
        else                            t = s[i] - 'A' + 10;
        int sum = 1;
        for(int j = 0; j < t; j++) sum += dp[j];
        dp[t] = sum;
    }
    for(int i = 0; i <= 15; i++) ans += dp[i];
    cout << ans;
}

递推（dp)，a[i]表示以i结尾的字符串 的最大方案数是多少。因为要递增，所以假设最后一位是x,那么以x结尾的字符串的最大方案数就是前面以1~x-1的结尾的方案数的总和，对吧？为什么sum初始化为1?因为本身只有自己的情况下就是一种方案。感觉还是有点像数位dp。。。