当前位置: 代码迷 >> 综合 >> 牛客网多校练习赛1 E Removal (计数dp)*
  详细解决方案

牛客网多校练习赛1 E Removal (计数dp)*

热度:43   发布时间:2023-11-15 16:39:24.0

链接:https://www.nowcoder.com/acm/contest/139/E
来源:牛客网
 

题目描述

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

输入

复制

3 2 2
1 2 1
4 2 2
1 2 1 2

输出

复制

2
4

备注:

* 1 ≤ n ≤ 105
* 1 ≤ m ≤ min{n - 1, 10}
* 1 ≤ k ≤ 10
* 1 ≤ si ≤ k
* The sum of n does not exceed 106.
#include<iostream>
#include<algorithm>
#include<string>
#include<map>//int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
#include<set>//int gcd(int a,int b){return b?gcd(b,a%b):a;}
#include<vector>
#include<cmath>
#include<stack>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define ll long long
#define MAX 1000000000
#define ms memset
using namespace std;
const int mod=1e9+7;ll dp[maxn][11];
int a[maxn],nxt[maxn][11];
int n,m,k;
/*
题目大意:给定n个数,要求范围为1到k,删除m个数,
则要求计数出现的不同序列的个数。比赛时感觉这是动态规划,但是计数类型和状态转移性质
的观察还是不熟练。
首先分析计数的性质和特征(感觉有点像拓扑排序的原理),
如果计算好了(i,j),那么计数(i,j)可以累加到什么地方呢,
根据题解,在删除i位置元素的i到下一个同样的元素出现的地方之间的数
时可以构成一个新的序列,这样计数累加性质就出来了
(其实也是看了题解了,自己也没完全明白)。。。
*/int main()
{while(~scanf("%d%d%d",&n,&m,&k)){for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=k;i++) nxt[n][i]=n+1;for(int i=n;i>=1;i--){for(int j=1;j<=k;j++) nxt[i-1][j]=nxt[i][j];nxt[i-1][a[i]]=i;///为什么是这样的填充完毕?///在进入到i时其已经计算好了}memset(dp,0,sizeof(dp));dp[0][0]=1;for(int i=0;i<n;i++)for(int j=0;j<=m;j++)for(int l=1;l<=k;l++){int n1=nxt[i][l],n2=n1-i-1;///填充计数的思想,找一种状态的性质,然后从前往后推,推的过程是计数累加的过程if(n2+j<=m)  dp[n1][n2+j]=(dp[n1][n2+j] + dp[i][j])%mod;}ll ans=0;for(int j=0;j<=m;j++) ans=(ans+dp[n-j][m-j])%mod;printf("%lld\n",ans);}return 0;
}