递推 字符串

本文主要是介绍递推 字符串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/contest/11232/B
来源：牛客网

学姐最近喜欢上了编码，尤其是十六进制编码，但是学姐特别挑剔，在学姐眼中，只有逐位递增的编码才是一个优美的编码，比如12，58都是优美的编码，85，22则都不是优美的编码，现在学姐得到了一个编码串，她希望你告诉她该编码串里可查询到的所有不重复的优美的编码总个数，对于单个字符组成的编码，学姐总是认为这个编码是优美的，且优美的编码当中是允许存在前导零的

编码可查询的判定依据:在给定编码串ss中删去任意kk位字符(0≤k＜|s|)(0≤k＜∣s∣)，剩下字符不改变顺序组成一个新的编码s1s1，则认为s1s1可在ss中查询到，如0102中可查询的编码有0，1，2，00，01，02，10，12，010，012，002，102，0102
输入描述:
一个字符串s表示所给十六进制编码串（1≤|s|≤1000000）
（保证所给编码串与标准十六进制一致，编码串中仅可能出现0-9与A-F，不会有多余字符出现）
输出描述:
一个数，表示不重复计算的情况下优美的编码的总个数
示例1
输入
复制
001A
输出
复制
7
说明
七种方案分别为
0,01,0A,01A,1,1A,A

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
char s[1000001];
int dp[1000101];
int main()
{
    scanf("%s",s);
    int i,t,ans=0,m,j;
    t=strlen(s);
    for(i=0; i<t; i++)
    {
        if(s[i]>='0'&&s[i]<='9')
            m=s[i]-'0';
        else
            m=s[i]-'A'+10;
        int sum=1;
        for(j=0; j<m; j++)
            sum+=dp[j];
        dp[m]=sum;
    }
    for(i=0; i<=15; i++)
        ans+=dp[i];
    printf("%d\n",ans);
}

这篇关于递推 字符串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！