题意

给你一个数组让你在中间删去m个数
问有多少种不同的结果,答案对(1e9+7)取模

思路

简单dp
开一个三维dp,第一维表示当前是第几个数,第二维表示构成的序列最后一个数字是什么,第三维表示还可以删去几次

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod=1e9+7;
const int N=1e5+5;
int n,m,k;
ll dp[N][15][15],a[N]; 
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%lld",a+i);
        //清空 
        for(int i=0;i<=n;i++)
            for(int j=0;j<=11;j++)
                for(int kk=0;kk<=11;kk++)
                    dp[i][j][kk]=0;

        for(int i=1;i<=n;i++)
        {
            //当前这个数不删 
            for(int j=1;j<=k;j++)
                for(int kk=0;kk<=m;kk++)
                    dp[i][a[i]][kk]=(dp[i][a[i]][kk]+dp[i-1][j][kk])%mod;

            //前面的数全部删掉 
            if(i-1<=m)
                dp[i][a[i]][m-(i-1)]++; 

            //当前的数删掉 
            for(int j=1;j<=k;j++)
            {
                if(j==a[i])//避免重复计算 
                    continue;
                for(int kk=1;kk<=m;kk++)
                    dp[i][j][kk-1]=(dp[i][j][kk-1]+dp[i-1][j][kk])%mod;        
            }
        }


        ll sum=0;
        for(int i=1;i<=k;i++)
            sum=(sum+dp[n][i][0])%mod;
        printf("%lld\n",sum);
    }
    return 0;
}