每日一题 4.27 Removal
Removal
https://ac.nowcoder.com/acm/problem/17137
这是一道二维dp题
我们用 dp[i][j] 来表示 前i个元素中删除j个
如果不考虑重复的话 dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 分别是删不删除当前数
考虑到重复 重复的诞生是这一序列的第i个元素与前面的x位置相同
那么就是以 a[x] 结尾的序列都能通过删除[x,i-1]这一段元素重新获得
于是有 dp[i][j]-=dp[x-1][j-(i-x)]
#include <bits/stdc++.h>
#define ll long long
int const N=1e5+5;
int const mod=1e9+7;
using namespace std;
int z[11],dp[N][11];
int main()
{
int n,m,k,x;
while(~scanf("%d%d%d",&n,&m,&k)) {
for(int i = 0;i <= k;++i) z[i] = 0;
dp[0][0] = 1;
for(int i = 1;i <= n;++i) {
scanf("%d",&x);
dp[i][0] = 1;
for(int j = 1;j <= min(m,i);++j)
{
dp[i][j] = dp[i - 1][j - 1] % mod + dp[i - 1][j] % mod;///假设无重复
dp[i][j] %= mod;
if(z[x] && (i - z[x] <= j))
{
dp[i][j] -= dp[z[x] - 1][j - (i - z[x])];///j-(i-z[x])就是还有能删除那一段元素位置
dp[i][j] %= mod;
}
}
z[x] = i;
}
cout<<(dp[n][m] + mod) % mod<<endl;
}
return 0;
}每日一题题解 文章被收录于专栏
每日一题题解的汇集
