【每日一题】4月27日题目精讲 Removal

链接：

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

Bobo has a sequence of integers s1, s2, …, sn where 1 ≤ si ≤ k. Find
out the number of distinct sequences modulo (109+7) after removing
exactly m elements.

输入描述:

The input consists of several test cases and is terminated by
end-of-file. The first line of each test case contains three integers
n, m and k. The second line contains n integers s1, s2, …, sn.

输出描述:

For each test case, print an integer which denotes the result.

示例1
输入

输出

2
4

题意：

长度为n的一组数，每个数都大于等于1，小于等于k，现在删除里面m个数，问会出现多少种情况？

题解：

dp问题
dp[i][j]表示前i个数字删去j个数字之后有多少个不同的序列数
列出转移方程：f [ i ] [ j ] = f [ i - 1 ] [ j ] + f [ i - 1 ] [j - 1]
转移方程很经典，就是我们考虑当前这个数删不删，如果不删，那就是前i-1个数删去j个数，如果删去，那就是前i-1个数删去j-1个数
但是！但是！
这个题会出现重复情况
比如：513241
删去四个数，有可能是51也可能是51（*为被删去的数）
，这不就重复了
怎么去除重复？
发生重复说明当前这个第i位的w选上了，我们需要找上一个出现的w，如果以w结尾并且子串的长度和删后长度（i-j）相等的就是和dp[ i ] [ j ] 重复的，直接减去即可.
为什么呢？继续看我给的样例：… 5 1 3 2 4 1
先不管5之前的省略号，假设5是第一位
我们知道第二位和第六位都是1，两个i之间的距离是len=5（含两端），如果我们将两个1之间的数全部删去，就是5 1 * * * 1，再删除任何一个1，剩下的数就是重复的，你删去前面的1，剩下5 * * * * 1，删除后面剩下5 1 * * * * 。所以重复的部分就是第一个1前面的数与1所组成的序列。
加上省略号，5之前还有很多数，查重的话就是把省略号中（算上5）的方法数去掉
我们要用到：last[i]表示第i位的数w的上一次出现位置
能得到：
dp [ i ] [ j ] = d p [ i ] [ j ]− dp [ pre [ i ] − 1 ] [ j− ( i − pre [ i ] ) ]
dp [ pre [ i ] − 1 ] [ j− ( i − pre [ i ] ) ] ：就是重复情况
pre[i] - 1就是重复的数字上一次出现的位置的前一位
（i - pre [ i ] ）就是len-1，就是两个数之间的数全删去再加上删任意一个端点。
j-（len-1）就是把这些数删去后，还要删的数量，而要删的就是pre[i]-1之前的数
我可能讲的不是很明白，看代码吧

代码：

#include <bits/stdc++.h> 
using namespace std;
const int maxn = 1e5 + 2;
const int mod= 1e9+7;
int dp[maxn][12];
int a[maxn];
int pos[12], last[maxn];
void init()
{
   
	        for (int i = 0; i <= n; i++)
            dp[i][0] = dp[i][i] = 1;
}
int main() 
{
   
    int n, m, k,w;
    while (~scanf("%d%d%d",&n,&m,&k))
	{
   
        
		init();//初始化，不删去和全删去的都只有一种 
		memset(pos, 0, sizeof(pos));
        for (int i = 1; i <= n; i++) 
		{
   
            scanf("%d",&a[i]);
            last[i] = pos[a[i]];
            pos[a[i]] = i;
        }

        for (int i = 1; i <= n; i++) 
		{
   
             w = min(i - 1, m);
            for (int j = 1; j <= w; j++)
			{
   
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
                //不查重的情况 
                if (last[i] && i - last[i] <= j)//如果前面有重复的数字，并且所要删除的数字的数量要能够删去重复数字之间的数（加上一端重复的数）
                    dp[i][j] = (dp[i][j] - dp[last[i] - 1][j - (i - last[i])] + mod) % mod;
                //将重复部分去掉
            }
        }
        cout << dp[n][m] << endl;
    }
    return 0;
}