【每日一题】Removal

Solution

看数据范围, 显然是一道dp计数题
令 $dp[i][j]$ 表示前 $i$ 个数字中去除 $j$ 个数字的种类
那么有递推式子 $dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]$
但是这样子计算显然会有重复情况出现
本题的难点在于如何解决重复的
比如序列 $5,\ 1, \ 2,\ 3,\ 4,\ 1\$
删去区间 $[2, 5]$ 的数字和删去区间 $[3, 6]$ 得到的结果是一样的但是会被计算两次
注意到出现这种情况是因为出现了两个 $1$
即如果一个数字它出现两次, 那么可能就有重复情况出现
观察发现, 假设当前数字为 $k$ , 当前位置为 $pos1$ , 上一次出现的位置为 $pos2$
那么如果我们删去 $[pos2, pos1 - 1]$ , 剩下的方案都是重复的
直接减去这一部分即可, 于是递推式子改成了 $dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] - dp[last[j] - 1][j - (i - last[j])]$
我搞了一个序列自动机找上一个元素的位置
另外看到很多人的题解初始化的时候好像越界了为什么没有报错....

$n <= 1e5$ , 初始化 $dp[i][i] = 1$ 不会越界吗

Code

/*
  autor: Kurisu
  2020年4月28日19:02:14
*/
#include<bits/stdc++.h>
using namespace std;

const long long inf = 1e18;
const int N = 2e5 + 5;
const double eps = 1e-10;
const int mod = 1e9 + 7;
typedef long long ll;
ll dp[N][50];
int a[N];
int last[N][50];
int main() {
  int n, m, k;
  while(cin >> n >> m >> k) {
    for(int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    for(int i = 0; i <= 2 * n; i++) {
      for(int j = 0; j <= 10; j++) {
        dp[i][j] = last[i][j] = 0;
      }
    }
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= k; j++) {
        last[i + 1][j] = last[i][j]; // 序列自动机
      }
      last[i + 1][a[i]] = i;
    }
    for(int i = 0; i <= n; i++) dp[i][0] = 1; // 一个都不删 方案是1
    for(int i = 1; i <= n; i++) {
      for(int j = 1; j <= m; j++) {
        dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % mod;
        int la = last[i][a[i]];
        if(j >= i - la && la >= 1) {
          dp[i][j] = (dp[i][j] - dp[la - 1][j - (i - la)] + mod) % mod;
        }
      }
    }
    cout << dp[n][m] << "\n";
  }
}