【每日一题】Removal dp

题意：给出长度为n的序列 要求从中删去m个数 求可能序列个数是多少

思路：
用 来表示前i个数数里删去j个数的答案个数 那么很容易就可以想到 上一个阶段删除了j-1个+当前这一个 和 删除了j个两种情况

很明显 这样是会有重复的 我们用last[i]表示这个数最新一次出现的位置 如果说这个数之前出现过 并且 当前位置和last[i]位置之间维度j的范围是更大 说明这个是满足要求而且是被重复计算过得到需要减去 那前i个数就是 last[i] - 1 要删除的个数就是 j - (i - last[i]) 初始化状态dp[i][0] = 1 前i个数不动情况有1种

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 1e5 + 5 , mod = 1e9 + 7;

LL  dp[N][11], last[N] , a[N];

int main()
{
    ios::sync_with_stdio(0);

    int n , m , k ;

    while(cin >> n >> m >> k)
    {
        memset(dp,0,sizeof dp);
        memset(last,0,sizeof last);

        dp[0][0] = 1;

        for(int i = 1;i <= n; i ++)
        {
            cin >> a[i];

            dp[i][0] = 1;
        }

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

                if(last[a[i]] && j >= (i - last[a[i]]))
                    dp[i][j] = (dp[i][j] - dp[last[a[i]] - 1][j - (i - last[a[i]])] + mod) % mod;
            }

            last[a[i]] = i;
        }

        cout << dp[n][m] << '\n';
    }

    return 0;
}