【每日一题】Removal(4.27)
Removal
https://ac.nowcoder.com/acm/problem/17137
dp计数问题
先考虑简单一点的情况，如果允许重复的话，可以用dp[i][j]表示当前位置为i，并且删除了j个元素后的方法数，那么转移相当于考虑第i个位置的数选和没选两种情况，即dp[i][j] = dp[i-1][j] + dp[i-1][j-1],从i=1到n扫描一遍就可以得到答案了。
这道题要求不重复，如果用dp[i][j]表示当前位置为i，删除了j个元素后不重复的方法数，怎么转移呢？
如果还用dp[i][j] = dp[i-1][j-1]可能会引起重复，思考下引起重复的原因肯定是第i个位置的数选中，
那么我们只需要找到上一个a[i]出现的位置，以a[i]结尾并且子串的长度和i-j相等的就是和dp[i][j]重复的，直接减去即可.
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 1e5+7;
const int mod = 1e9+7;
int a[maxn],dp[maxn][11],l[11]; //l记录上一次出现的位置
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int n,m,k;
while(cin>>n>>m>>k)
{
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=0;i<=11;i++) dp[i][i] = 1; //全删除
for(int i=1;i<=n;i++) dp[i][0] = 1; //删除0个元素
memset(l,0,sizeof(l));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=min(i-1,m);j++)
{
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j])%mod;
int len = i-j; //字串的长度
if(l[a[i]])
{
int pos = l[a[i]];
int cnt = pos -len; //要删除的元素的个数
if(cnt>=0)
dp[i][j] = (dp[i][j]-dp[pos-1][cnt]+mod)%mod;
}
}
l[a[i]] = i;
}
cout<<dp[n][m]<<'\n';
}
return 0;
}
查看3道真题和解析
