Code（poj 1850）

时间：2024-04-25 18:34:57

大致题意：（与POJ1496基本一致）

输出某个str字符串在字典中的位置，由于字典是从a=1开始的，因此str的位置值就是 在str前面所有字符串的个数 +1

规定输入的字符串必须是升序排列。不降序列是非法字符串

不要求用循环输入去输入若干组字符串，但若输入非法字符串则输出0，且结束程序，这是和POJ1496最猥琐的区别，很多同学只注意到规定str的长度不同，以为把str数组长度改一下直接复制就能AC再多刷一题了，殊不知老是WA却找不到原因，大概就是这里出问题了

本题Str最长为10个字符

//数位DP   f[i][j]:以i开头的长度为j的个数

#include<cstdio>

#include<iostream>

#include<cstring>

#define M 30

using namespace std;

int f[M][M],a[M];

char c[M];

void F()

{

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

      f[i][]=;

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

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

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

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

}

int main()

{

    scanf("%s",c);

    int len=strlen(c),flag=;

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

    {

        a[i]=c[i-]-'a'+;

        if(a[i]<a[i-])flag=;

    }

    if(flag)

    {

        printf("");

        return ;

    }

    F();

    int ans=;

    for(int i=;i<=;i++)//求出前len-1位的个数

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

        ans+=f[i][j];

    //当到第i位时，字母一定比i-1大且比实际的小

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

      for(int j=a[i-]+;j<a[i];j++)

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

    printf("%d",ans+);//加上它自己

    return ;

}

相关文章