SPOJ_DSUBSEQ Distinct Subsequences

统计一个只由大写字母构成的字符串的，子串数目，这里指的是子串不是子序列，可以不连续，请注意

然后我按照计数DP的思想，dp[i][j]表示长度为i的子串，最后一个字母为j

然后为了去重，每一次dp的时候，记录这个时候最后一位所在的位数，而且之前用一个后缀记录之后有没有该字母，这样每次，从上一次的j所处的位置的下一个看看后缀有没有这个字母，合法的话就 dp[i][j]+=dp[i-1][k]。

但是这个方法有个超大的漏洞，就是去重的问题，我为了防止重复，虽然用了后缀记录后面有没有这个字母，但是在加的时候，我是统一加的，即不管后面有没有字母，我直接统一+dp[i-1][j]，导致结果到了后面就不行了，而且这个方法会超时，我当时虽然期待他超时的，没想到返回个WA了

其实可能是因为最近计数DP做的多了的结果，这个其实用一维就可以了，从前往后扫，对当前字母，我的值即为 dp[i-1]+添加当前字母之后产生的新子串

这个新子串的个数分两种情况，

1。该字母之前未出现过，则新个数=dp[i-1]+1,表示当前字母加上后使得前面的dp[i-1]个串又能产生新的子串，+1是指自己本身单个字母。

2.该字母之前出现过，则要判断重复了，其实就是 dp[i-1]-dp[lastoccur-1];即先加上dp[i-1]但肯定是有重复的，为了去重，找到上次出现该字母的那个地方，减去那个地方就可以去重了

要注意的是，这个里面出现了减法，而答案是要取模的，所以这种相减是可能出现负数的情况的（这个地方确实之前没想到，没注意，我还纳闷怎么其他人都有个判断负值的操作），就是因为取模里面有减法，所以是可能出现负数的，注意这种情况

#include <cstdio>

#include <iostream>

#include <cstring>

#define LL long long

using namespace std;

const int N = ;

const LL M = ;

char str[N];

LL dp[N];

int lasts[];

int main()

{

    int t;

    scanf("%d",&t);

    while (t--)

    {

        scanf("%s",str+);

        int len=strlen(str+);

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

            dp[i]=;

        }

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

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

            dp[i]=dp[i-];

            if (lasts[str[i]-'A']>){

                dp[i]+=dp[i-]-dp[lasts[str[i]-'A']-];

                while (dp[i]<) dp[i]+=M;

            }

            else{

                dp[i]+=dp[i-]+;

            }

            lasts[str[i]-'A']=i;

            if (dp[i]>=M) dp[i]%=M;

        }

        dp[len]++;

        dp[len]%=M;

        printf("%lld\n",dp[len]);

    }

    return ;

}

巴特西

SPOJ_DSUBSEQ Distinct Subsequences

最新文章

热门文章