Removal

这是一道经典dp 的题目！

题目意思大致就是: 给出一个序列，问你任意删除m个字符，有不同种方案？ 每个数字的范围在k之内。

我们可以设 dp[i][j] 表示前i个元素删除j个元素后的方案数 很容易推出dp方程:

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

意思就是 前i个元素删j个=要么我这个i位置的数不删，那么就从前i-1个数中删j个，或者我这个i位置给他删掉，那么就从前i-1个数中删j-1个，(因为i位置被删了，所以只要删j-1个就够了)

但是会出现重复的情况，比如 下面这个例子 1 2 4 5 6 7 4

比如我们i跑到了第7个位置，此时a[7]=4.我们可以发现，如果删掉4 5 6 7或者删掉5 6 7 4.那么剩下的都为1 2 4. 这样的方案就发生重复了。

然后刚刚上面计算的是所以情况（包含重复的) ，利用容斥定理剪掉重复的部分就是我们的答案 。。

我们可以发现，第一个4和第二个4之间的数是一定要删完的，然后才会产生重复，重复的方案就是=dp[pos-1][j-(i-pos)] pos表示前面第一个和a[i]相同的数的位置。我们删掉了i-pos个数，j-(i-pos)表示剩下还需要删的，也就是说，在前pos-1个数中，删j-（i-pos）个数，就是重复的。

AC代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;

const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}

const int N=1e5+100;
const int M=15;

int dp[N][M];//dp[i][j]表示前i个数删掉j个数的方案 
int n,m,k2;

int a[N];

int main()
{
    while(~scanf("%d%d%d",&n,&m,&k2))
    {
        memset(dp,0,sizeof(dp));
        for(int i=0;i<=n;i++)
        {
            dp[i][0]=dp[i][i]=1;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
                int pos=0;
                for(int k=i-1;k>=1;k--)
                {
                    if(a[i]==a[k])
                    {
                        pos=k;
                        break;
                    }
                }
                if(i-pos<=j&&pos-1>=0)dp[i][j]=(dp[i][j]-dp[pos-1][j-(i-pos)]+mod)%mod;
            }
        }
        printf("%d\n",dp[n][m]%mod);
    }
    return 0;
}