【每日一题】Removal

这个题是将长度为n的序列里面删去m个元素，问你有多少种剩下来的序列情况。
很容易联想到dp
首先如果两两都不同，那么直接01背包

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

但是题目里面有可能会出现重复元素，这个时候就要去剪掉一些方案数了。
我们记录下来每一个数前面最近的值相同的元素的pos位置，从前到后扫一遍就可以得到。
然后我们计数的时候，要加一个判断。如果dp[i][j]此时的pre[i]=k&&j>=(i-k),那么就要减去一部分

dp[i][j]=(dp[i][j]-dp[k-1][j-(i-k)]+mo)%mo;

具体见代码吧

#include<bits/stdc++.h>
using namespace std;
int dp[100010][100],a[100010],last[100010],pre[100010];
int main()
{    int n,m,k;
    while(cin>>n>>m>>k)
    {
        memset(last,0,sizeof(last));
        memset(pre,0,sizeof(pre));
         for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;++i)
    {
        pre[i]=last[a[i]];
        last[a[i]]=i;         //更新当前
    }
    for(int i=0;i<=n;i++) dp[i][0]=dp[i][i]=1; //初始化
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=min(m,i);j++){
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%(1000000007);
            if(pre[i]!=0&&j>=(i-pre[i])){
                int k=pre[i];
                dp[i][j]=(dp[i][j]-dp[k-1][j-(i-k)]+1000000007)%1000000007;
            }
        }

    }
    cout<<dp[n][m]<<endl;
    }



    return 0;
}