题目链接
NC17137
思路
DP状态定义为dp[i][j]表示前i个数删除j个后的答案。那么很容易得到递推方程
1
| dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
|
就是删除当前这个和不删除当前这个的情况，然后如果是 1 2 3 5 6 7 8 5 m=4的话，就会出现删除5 6 7 8 和删除6 7 8 5的情况重复的情况，我们需要减去重复的这部分，观察到重复的这部分需要把6 7 8给删除，就是把两个5之间的数全给删除了，于是重复的这部分就是dp[pos-1][j-(i-pos)]就代表中间的全部给删除了。
代码实现
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int dp[N][15],pos[15];
const int mod = 1e9+7;
int main(){
int n,m,k;
while(cin>>n>>m>>k){
memset(dp,0,sizeof(dp));
memset(pos,0,sizeof(pos));
dp[0][0]=1;
for(int i=1;i<=n;i++){
int x;
cin>>x;
dp[i][0]=1;
for(int j=1;j<=min(m,i);j++){
dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
if(pos[x]&&j-i+pos[x]>=0){
dp[i][j]=(dp[i][j]-dp[pos[x]-1][j-i+pos[x]]+mod)%mod;
}
}
pos[x]=i;
}
printf("%d\n",dp[n][m]);
}
}
|