[每日一题] 4.27 Removal

题意：

解法：

for(int i=1;i<=n;i++){
    //枚举第i个数字前面i-m个位置，是否存在相同的数字
    for(int j=i;j>=max(1,i-m);j--){
          b[j] = (b[j]%mod + b[j-1]%mod - dp[j][a[i]] + mod)%mod;
          dp[j][a[i]] = b[j-1];
    }    
}

时间复杂度：

std：

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 100005;
ll dp[maxn][12],b[maxn];
int a[maxn];
const ll mod = 1e9 + 7;
int main()
{
    int n , m , k;
    b[0] = 1;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            b[i] = 0;
            for(int j=1;j<=k;j++)
                dp[i][j] = 1ll*0;
        }
        for(int i=1;i<=n;i++){
            for(int j=i;j>=max(1,i-m);j--){
                b[j] = (b[j]%mod + b[j-1]%mod - dp[j][a[i]] + mod)%mod;
                dp[j][a[i]] = b[j-1];
            }    
        }
        printf("%lld\n",b[n-m]);
    }
    return 0;
}