题意：长度为n的字符串，删掉m个字符后有多少种不同的字串。
解题思路：dp[i][j]表示加入第i个数字后，总共删掉j个数字时，有多少种不同的序列。假设不考虑有重复的情况，dp方程为：dp[i][j]=dp[i-1][j] (第i个数字不删)+dp[i-1][j-1] (第i个数字删)。
现在考虑重复的情况。
如果前面有与a[i]相同的数字a[k] (k小于i)，并且i-k<=j，就会产生重复。
比如：cdeaae(用字符串举例比较方便),假设现在是i=6,j=4。那么我们需要dp[6][4]-dp[2][1]。
那么为什么不是减掉dp[3][1]呢?
因为dp[3][1]=dp[2][1]+dp[2][0]，也就是说dp[3][1]还包括了删掉a[3]的状态，而如果删掉a[3]，那么加入a[6]的时候就不会有重复了。所以减掉dp[2][1]，就是减掉了a[3]不删除的情况。
附ac代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int maxx = 2 * 1e3;
int nu[maxn];
int pos[11];
int pre[maxn];
ll dp[maxn][11];
int main()
{
int n, m, k;
while(~scanf("%d %d %d", &n, &m, &k))
{
memset(pos, 0, sizeof(pos));
memset(pre, 0, sizeof(pre));
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; ++i)
{
scanf("%d", &nu[i]);
pre[i] = pos[nu[i]];
pos[nu[i]] = i;
}
for(int i = 1; i <= n; ++i)
{
dp[i][0] = 1;
}
for(int i = 0; i <= m; ++i)
{
dp[i][i] = 1;
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= min(n - 1, 10); ++j)
{
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
if(pre[i] && (i - pre[i]) <= j)
{
dp[i][j] = (dp[i][j] - dp[pre[i] - 1][j - (i - pre[i])] + mod) % mod;
//j-(i-pre[i])是指在不删去重复元素pre[i]时，前面还要删除的个数
}
}
}
printf("%lld\n", dp[n][m]);
}
return 0;
}