牛客网暑期ACM多校训练营（第一场）E 题解

题意:长度为n的字符串，删掉m个字符后有多少种不同的字串。

思路:看到这题应该可以想到dp。n的范围1e5，m只有10，那么我们可以用dp[i][j]表示前i个字符构成的子串删掉j个字符后有多少种不同的串。

我们可以推出方程:dp[i][j]=dp[i-1][i-1]+dp[i-1][j-1].但是如果前面有与a[i]相同的字符a[k] (k<i)，并且i与k的位置距离小于等于j，那么就会产生重复。

举个例子cdeaaaemkl

当我们i=7,j=4时,a[3]=a[7],那么如果删掉中间的[eaaa]字串就会变成[cde] (注意i=7，所以不是cdemkl)，因为我们已经在前面

i=3时算过了一次[cde]这种情况，所以我们需要dp[7][4]-dp[2][0](仔细想想为什么要减去dp[2][0]而不是dp[3][0]).

下面给出代码，不加读入优化会T，我也不造为什么。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const ll mod=1e9+7;
ll dp[100005][15];
int pre[100005];
int now[100005];
int a[100005];

int main()
{
    int n,m,k;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        memset(pre,0,sizeof(pre));
        memset(now,0,sizeof(now));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            pre[i]=now[a[i]];
            now[a[i]]=i;
        }
        for(int i=0;i<=m;i++) dp[i][i]=1;

        for(int i=1;i<=n;i++)
        {
            dp[i][0]=1;
            int d = i - pre[i];
            for(int j=1;j<=m&&j<i;j++)
            {
                dp[i][j]=((dp[i-1][j]+dp[i-1][j-1])%mod+mod)%mod;
                if(pre[i]!=0&&d<=j)
                {
                    dp[i][j]=((dp[i][j]-dp[pre[i]-1][j-d])%mod+mod)%mod;
                }
            }
        }
        printf("%lld\n",dp[n][m]);
    }
    return 0;
}