链接：https://www.nowcoder.com/acm/contest/139/E
来源：牛客网 Bobo has a sequence of integers s1, s2, ..., sn where ≤ si ≤ k.
Find out the number of distinct sequences modulo (+) 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
输入
复制 输出
复制 备注:
* ≤ n ≤
* ≤ m ≤ min{n - , }
* ≤ k ≤
* ≤ si ≤ k
* The sum of n does not exceed .
dp [i][j]：表示以i位子结尾删除j个字符的方案数。
开一个nt[i][j] 表示从i开始，字符j的位子
那么我们可以得到一个递推式。
dp[nt[i][p]][nt[i][p]-i-1+j]+=dp[i][j];
dp[i][j]可以转移到下一个位子;
比如
XXXCYYYC；
那么我们删到xxx和xxxcyyy是一样
所以我们每次找到下一个位子
#include <iostream>
#include<stdio.h>
#include<string.h>
#define ll long long
#define mod 1000000007
using namespace std;
int nt[][];
int a[];
int dp[][];//以a[i]结尾的，删了 j个
int main()
{
int n,m,k;
while(~scanf("%d%d%d",&n,&m,&k))
{
for(int i=; i<=n; i++)
{
scanf("%d",&a[i]);
}
for(int i=; i<=k; i++)
{
nt[n][i]=n+;
}
for(int i=n; i>=; i--)
{
for(int j=; j<=k; j++)
nt[i-][j]=nt[i][j];
nt[i-][a[i]]=i;
}
memset(dp,,sizeof dp);
dp[][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
for(int p=;p<=k;p++)
{
int to=nt[i][p];
int shan=to-i-;
if(shan+j<=m)
{
dp[to][shan+j]+=dp[i][j];
dp[to][shan+j]=dp[to][shan+j]%;
}
}
}
}
int ans=;
for(int i=;i<=m;i++)
{
ans=ans+dp[n-i][m-i];
ans=ans%;
}
cout<<ans<<endl; } return ;
}