Removal题解

题意：N个数，删除M个数字，所有的数字都是小于K。
问你最后有几种子序列。
题解：首先数据范围一看可以DP，然后我们就要想表达式。
如下：DP[i][j]=dp[i-1][j-1]+dp[i-1][j];
翻译：当我加入第i个数的是时候，我删除j个数。等于符号后面的是由上一次的继承下来，首先我本次的第i个数删除，那么就还有j-1个数删除，也就是第i个数删了，之后是第i个数不删，删除前面的j个。
这样一来我们是不是就是把所有的子序列都搞出来，但是我们在这个过程中会有重复的计算，列如，1 2 3 2 4 3，当我们i=6，j=4,那么是不是删除324，和删除243会得到相同的子序列，这时候就是重复了，那么如何处理呢，首先我们每次把每个数都记录下来，判断这个数字在上次的那个位置出现，那么是不是就有这个k(上次出现此数的位置)，使用上面的i,j,我们要想知道是否删除数字会不会重复，是不是应该 判断i-k和j的大,如果小于说明k-i的中间删除了都还有数字可以删除，对吧，这时候就有重复的了，dp[6][4]=dp[5][4]+dp[5][3]这是总的个数，之后我们如何减去重复的呢，是不是就应该回到上一个重复的数那里，i-k=6-3=3,中间加上第i个一共有三个数，是不是我们还要删除一个，怎么办，是不是就是删除K前面的，这个时候还有一个数需要删除，我们就是dp[3][1],对吧，为什么我们不能直接dp[6][4]-dp[3][1]呢，想想，dp[3][1]=dp[2][1]+dp[2][0],代表我前面的3是不删和删，然后dp[6][4]=dp[5][4]+dp[5][3],代表后面的3是不删还是删，这样一看我dp[6][4],是由前面的继承下来的 那么是不是应该减去dp[2][1];然后最后注意mod的不要溢出。

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
int ans[maxx];
int last[maxx];
int p[maxx];
int dp[maxx][15];
int main()
{
    fio;
    int n,m,k;
    while(cin>>n>>m>>k)
    {
         mse(last,0);
         mse(p,0);
        for(int i=1; i<=n; i++)
        {
            cin>>ans[i];
            p[i]=last[ans[i]];
            last[ans[i]]=i;
        }
        for(int i=0; i<=n; i++)
       {
       dp[i][i]=1;

       }
        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-1]+dp[i-1][j])%mod;///删除第i个数+不会删除第i个数
                if(p[i]!=0&&i-p[i]<=j)
                {
                    dp[i][j]=(dp[i][j]-dp[p[i]-1][j+p[i]-i]+mod)%mod;

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