题目

题目描述： 
Bobo有整数s1，s2，...，sn，其中1 ≤ si ≤ k。
删除m个元素，找出整数和对（1e9 + 7）取模，大小不同的方法数。

输入描述：
输入包含多个测试用例，并以文件结尾终止。
每个测试用例的第一行包含三个整数n，m和k。
第二行包含n个整数s1，s2，...，sn。

输出描述：
对于每个测试用例，请打印一个表示结果的整数。

解析

这道题毫无疑问就是到dp的题目（又是我不擅长的）
  • 还是要说：动态规划的基础就是递推。
但是这道题最麻烦在大小相同的时候有相同意义的子集（相同意义指整数和取模相同）。

我们先来理解一下题目操作：
  1. 根据dp思想，我们先把不考虑查重的方法数求出来，再进行查重。所以我们在这里假设一个二维dp数组（dp[x][y]的意思前x个数中删除y个数的方法数）
  2. 然后根据递推思想，我们要在知道第pos个的时候（删除del个数）怎么才能得到第pos+1个（删除del+1个数）：
    我们将dp[pos+1][del+1]分成两种情况：<1>假如我们删除第pos+1个数，就有dp[pos][del]种情况；<2>假如不删第pos+1个数，就有dp[pos][pos + 1]种情况。
    所以易得：dp[pos + 1][pos + 1] = dp[pos][del] + dp[pos][pos + 1]。
  3. 以上是不查重的情况，接下来我们就要进行查重操作：我们什么时候会有重复的情况呢？当然就是在有重复数字的时候。
  4. 假如有一个数表【……，1，2，3，4，5，1】。（以下以该数表举例）
  5. 根据递推思想，我们是一路推出来的，所以只要知道某点的上一个相同位置就行了。也就是表中的两个1。（假设其包括端点之间的距离为len）
  6. 我们可以知道，拿重复段来说：如果再删去任意len-1个数就会重复（删除1,2,3,4,5和2,3,4,5,1）。
  7. 然后我们第6条是建立在前面的数（“……”中的那些数）删除的都相同的情况下。所以查重只要删除一遍“……”中的方法数就行。
  8. 这里我们用一个数组（last数组）表示某一个节点上一个相同节点的位置。就可以得到dp[i][j] = dp[i][j] - dp[last[i] - 1][j - (i - last[i])]。

既然我们知道了方法（我方法好像写的太长了），下面就是编程了：
  1. 先要初始化s（数据数组）和last（上一个位置的数组）。因为要记录上一个相同数的位置，我们可以定义一个散列数组（mem数组），用来表示某一个数所在的位置（碰到就更新）。
  2. 然后我们要确定我们的dp初始条件：我们删除所有数和不删除任何一个数的方法数都是1。
  3. 然后再进行递推求解就好啦。因为都是都pos位置前面的位置进行操作，所以我们递推和查重可以同时进行。
  4. 详细看代码趴~

AC代码 

#include <iostream>
#include <cstring>
using namespace std;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MOD = 1e9 + 7;
const int MAX = 1e5 + 7;
int dp[MAX][10 + 7];
int s[MAX], mem[10  +  7], last[MAX];
//全局变量区

int main() {
    js;
    int n, m, k;
    while (cin >> n >> m >> k) {
        memset(mem, 0, sizeof(mem));
        for (int i = 1; i <= n; i++) {
            cin >> s[i];
            last[i] = mem[s[i]];
            mem[s[i]] = i;
        }
        //初始化s条件数组和last位置数组
        for (int i = 0; i <= n; i++)
            dp[i][0] = dp[i][i] = 1;
        //初始化dp数组：不删数和全删都是一种情况
        for (int i = 1; i <= n; i++) {
            int del = min(i - 1, m);
            for (int j = 1; j <= del; 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;
}
//函数区