牛客网暑期ACM多校训练营(第一场)E、Removal 题解

E题解法:
这题相当于求有多少种不同的长度为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;
}
全部评论

相关推荐

神哥不得了:神哥来啦~1.建议不要包装,很容易问穿2.没日常也能找到暑期3.简历模板换一下,字体和版式看着好难受,而且最好压缩到一页,技术的倒数第2和3重复啦,项目建议换两个高质量的上去,如果时间够的话,八股就把高频top50的题目多巩固几遍,吃透,注意不要找假高频,这样绝对能找到暑期
点赞 评论 收藏
分享
落叶随风呀:学校不好就放两栏,专业能力往前移, 政治面貌不是党员不如不写,籍贯湖南衡阳,或者湖南,浅尝辄止 基本信息排版不够美观,没有对齐 简历上花里胡哨的东西去掉 项目我不评价,因为我能力有限,且对mcu了解不足 但是这份简历掌握的水平,你可以海投试试,工作没问题但是工资应该不会高,因为搞mcu的小公司多
点赞 评论 收藏
分享
评论
21
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务