数位DP || Gym 101653RRamp Number

每一位都大于等于前一位的数叫Ramp Number

给一个数，如果不是Ramp Number输出-1，如果是Ramp Number输出比它小的Ramp Number的个数

只和每一位上的数字有关

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <queue>

#include <algorithm>

using namespace std;

char s[];

long long f[][];//数位dp

int main()

{

    int T;

    scanf("%d", &T);

    memset(f, , sizeof(f));

    for(int i = ; i <= ; i++) f[][i] = ;

    for(int i = ; i <= ; i++)

    {

        for(int j = ; j <= ; j++)

        {

            for(int k = j; k <= ; k++)

                f[i][j] += f[i - ][k];

        }

    }

    /*f[i][j]表示长度为i以j开头的这样的数有多少个

     *f[i][j] = sum(f[i-1][k]) k>=j

     *例如f[3][5] 表示长度为3，以5开头的上升数的个数 即333,334,335,336……

     *只看后两位 33,34,35…… 44,45,46……

     *是长度为2，以3开头的+长度为2，以4开头的+……

     */

     /*

      *加的时候如1345 -> f[4][0] + f[3][1] + f[3][2] + f[2][3] + f[2][4] + f[1][4] + f[1][5]

      *f[4][0] 所有一二三位数，然后固定第一位是1

      *f[3][x] (x >= 1 && x < 3) 取的这些三位数后在前面放1就是结果，然后固定第二位是3

      *以此类推

      */

    while(T--)

    {

        scanf("%s", s);

        int len = strlen(s);

        int flag = ;

        for(int i = ; i < len; i++)

        {

            if(s[i] < s[i - ])

                flag = ;

        }

        if(!flag)

        {

            printf("-1\n");

            continue;

        }

        long long ans = ;

        for(int i = ; i <= len; i++)

        {

            for(int j = i == ?:s[i-] - ''; j < s[i-] - ''; j++)

            {

                ans += f[len-i+][j];

            }

        }

        printf("%lld\n", ans);

    }

    return ;

}