每日一题Day5

题解：
dp题目但是还是太菜了...
我们定义状态函数为前i个元素中删去j个元素后得到的子序列数目，如果不考虑重复，就有。但是这样转移的话会有重复序列的情况出现，比如1 2 1序列，删除和删除是一样的结果。那么我们发现，出现重复的情况的前提是**当前元素有重复元素且两者之间的元素和其中一个全部被删除。**
于是可以更新一下转移方程：其中past是上一次出现的位置。

AC代码：

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:4996)
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define me(a,b) memset(a,b,sizeof(a))
#define PII pair<int,int>
#define ull unsigned long long
#define ios std :: ios :: sync_with_stdio(false)
#define rep(i,a,b) for(int i = a;i <= b;i ++)
#define esp 1e-16

using namespace std;

const int maxn = 1e5 + 9;
const int mode = 1e9 + 7;

ll dp[maxn][12] = {};
int n, m, k;
int a[maxn] = {}, pre[maxn] = {};

int main()
{
    ios;
    while (cin >> n >> m >> k) {
        me(dp, 0);
        me(pre, -1);
        rep(i, 1, n) cin >> a[i];
        dp[0][0] = 1;
        rep(i, 1, n) {
            dp[i][0] = 1;
            rep(j, 1, min(m, i)) {
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] + mode) % mode;
                if (pre[a[i]] != -1 && (i - pre[a[i]]) <= j) dp[i][j] = (dp[i][j] - dp[pre[a[i]] - 1][j - (i - pre[a[i]])] + mode) % mode;
            }
            pre[a[i]] = i;
        }
        cout << dp[n][m] << endl;
    }
    return 0;
}