牛客网暑期ACM多校训练营（第一场）E、Removal 题解
E题解法:
这题相当于求有多少种不同的长度为n-m的子序列。
我们可以用dp来求解。
我们定义dp[i][j]代表长度为i，最末尾的数字为j的子序列方案数,sum[i]代表长度为i的子序列个数
我们初始令sum[0]=1
很容易写出O(n^2)复杂度的解法
然后怎么优化呢，我们发现，每次sum[j]和dp[j]只会由sum[j-1]和dp[j-1]推出来，而我们需要的只有sum数组的倒数第m个数字，m又非常小。
这时候一个很简单的优化就出来了
这题相当于求有多少种不同的长度为n-m的子序列。
我们可以用dp来求解。
我们定义dp[i][j]代表长度为i，最末尾的数字为j的子序列方案数,sum[i]代表长度为i的子序列个数
我们初始令sum[0]=1
很容易写出O(n^2)复杂度的解法
for(int i=1;i<=n;i++){//每次增加一个字符
for(int j=i;j>=1;j--){//从长到短枚举子序列长度
sum[j]+=(sum[j-1]-dp[j][s[i]])%mod;//因为dp[j][s[i]]要等于sum[j-1]，这样长度为j的子序列方案数发生了变化，所以我们要修改sum[j]的值
sum[j]%=mod;
dp[j][s[i]]=sum[j-1];
}
} 最终的sum[n-m]就是我们要求的答案然后怎么优化呢，我们发现，每次sum[j]和dp[j]只会由sum[j-1]和dp[j-1]推出来，而我们需要的只有sum数组的倒数第m个数字，m又非常小。
这时候一个很简单的优化就出来了
for(int i=1;i<=n;i++){//每次增加一个字符
for(int j=i;j>=1&&j>=i-m-1;j--){//从长到短枚举子序列长度，这里只需要维护最后m个就行了，保险起见我***护了一个数。
sum[j]+=(sum[j-1]-dp[j][s[i]])%mod;//因为dp[j][s[i]]要等于sum[j-1]，这样长度为j的子序列方案数发生了变化，所以我们要修改sum[j]的值
sum[j]%=mod;
dp[j][s[i]]=sum[j-1];
}
} 只要在第二层for里加一个限制条件就好了，我们只dp最后m个数字，而之前的是我们不需要的，这样一个O(n*m)复杂度的算法就出来了。注意取模就可以AC啦
完整代码
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
int s[111111];
int dp[111111][11],sum[111111];///长度为i 结尾为j
///
int main(){
int n,m,k;
while(~scanf("%d%d%d",&n,&m,&k)){
for(int i=1;i<=n;i++){
scanf("%d",s+i);
}
memset(sum,0,sizeof(sum));
memset(dp,0,sizeof(dp));
sum[0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j>=1&&j>=i-m-1;j--){
sum[j]+=(sum[j-1]-dp[j][s[i]])%mod;
sum[j]%=mod;
dp[j][s[i]]=sum[j-1];
}
}
int ans=sum[n-m]%mod;
ans+=mod;
ans%=mod;
printf("%d\n",ans);
}
return 0;
}
联想公司福利 498人发布
腾讯二面852人在聊
查看20道真题和解析
投递小红书等公司10个岗位 >