Removal

题意:给定n个会有重复数字,删除m个问有多少种序列,然后取模
题解:dp
构建状态转移方程 在第i个位置,要删除j个数字,那么要不前i-1位已经删除j个数字,要不前i-1位已经删除j-1个数字,第i再删除
当然如序列 此时我们要删除5个数字,会出现 和 的重复
所以应该去重,即 , 表示与第i位相同的数字,上一次出现的位置,然后具体的解释,参照第一个式子的解释
时间复杂度:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

#define mod 1000000007
const int maxn=100010;

int num[maxn];
int pre[maxn],last[maxn];

int dp[maxn][20];
int main()
{
        int n,m,k;
        while(~scanf("%d%d%d",&n,&m,&k))
        {

            memset(last,0,sizeof(last));

            for(int i=1;i<=n;i++)
            {
                scanf("%d",&num[i]);
                pre[i]=last[num[i]]; ///表示在之前与当前数字相同的位置是哪个
                last[num[i]]=i; ///表示当前数字的位置
            }

            for(int i=0;i<=m;i++) dp[i][i]=1; ///表示在前i个数字中，删掉全部有多少种不同序列，
                                            ///切记从0开始初始化
            for(int i=1;i<=n;i++)
            {
                dp[i][0]=1;///表示不删掉数字

                for(int j=1;j<=min(i-1,m);j++)
                {
                    dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%mod;

                    if(pre[i]&&i-pre[i]<=j){
                        dp[i][j]-=dp[pre[i]-1][j-(i-pre[i])]; ///dp[pre[i]-1][j-(i-pre[i])]中，pre[i]-1,表示不删掉pre[i],
                        ///j-(i-pre[i]) 表示把两个相同数字之间的其它数字删掉也还不够，需要在往前删掉j-（i-pre[i])个数字才行
                        dp[i][j]%=mod;
                        dp[i][j]=(dp[i][j]+mod)%mod; ///防止负数取模
                    }
                }
            }

            printf("%d\n",dp[n][m]);


        }
        return 0;
}