每日一题 4.27 Removal

这是一道二维dp题
我们用 dp[i][j] 来表示 前i个元素中删除j个
如果不考虑重复的话 dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 分别是删不删除当前数
考虑到重复 重复的诞生是这一序列的第i个元素与前面的x位置相同
那么就是以 a[x] 结尾的序列都能通过删除[x,i-1]这一段元素重新获得
于是有 dp[i][j]-=dp[x-1][j-(i-x)]

#include <bits/stdc++.h>
#define ll long long
int const N=1e5+5;
int const mod=1e9+7;
using namespace std;
int z[11],dp[N][11];
int main()
{
    int n,m,k,x;
    while(~scanf("%d%d%d",&n,&m,&k)) {
        for(int i = 0;i <= k;++i) z[i] = 0;
        dp[0][0] = 1;
        for(int i = 1;i <= n;++i) {
            scanf("%d",&x);
            dp[i][0] = 1;
            for(int j = 1;j <= min(m,i);++j)
            {
                dp[i][j] = dp[i - 1][j - 1] % mod + dp[i - 1][j] % mod;///假设无重复
                dp[i][j] %= mod;
                if(z[x] && (i - z[x] <= j))
                {
                    dp[i][j] -= dp[z[x] - 1][j - (i - z[x])];///j-(i-z[x])就是还有能删除那一段元素位置
                    dp[i][j] %= mod;
                }
            }
            z[x] = i;
        }
        cout<<(dp[n][m] + mod) % mod<<endl;
    }
    return 0;
}