多校(第一场)E-Removal

这题挺多人已经补了,还是说下我对官方题解做法的理解
状态定义:dp[i][j]表示从前i个数字中删去j个数字且以s[i]结尾的不同序列个数
转移的思路:在dp[i][j]状态,考虑增加一个数字c,假设i位置后面的原序列是这样,xxxc1yyyyc2,其中x、y是任意是非c的数字,如果这个c是c1,那要删除xxx,如果这个c是c2,那要删除xxxc1yyyy,由于加哪个c结果都一样,为了不算重复,只算i位置后的第一个c
转移:next(i, c)表示位置 i 后第一个字符 c 的位置,枚举下一个字符c,从dp[i][j]转移到dp[ next(i, c) ] [ j + next(i, c) - i - 1],(和官方题解有点不一样)
    for(int i = 0;i<=n;i++){
        for(int j = 0;j<=m;j++){
            if(!dp[i][j]) continue;
            for(int c = 1;c<=k;c++){
                int del = j + nxt[i][c] - i - 1;
                if(del <= m){
                    dp[nxt[i][c]][del] += dp[i][j];
                    dp[nxt[i][c]][del] %= mod;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) if(0<=i-n+m && i-n+m <= m) ans = (ans + dp[i][i-n+m])%mod;


全部评论
算答案为啥不从n-m开始循环。。。
点赞 回复 分享
发布于 2018-07-21 21:33

相关推荐

码农索隆:有点耳熟,你们是我教过最差的一届
点赞 评论 收藏
分享
陆续:不可思议 竟然没那就话 那就我来吧 :你是我在牛客见到的最美的女孩
点赞 评论 收藏
分享
06-07 17:17
嘉兴学院 教师
心爱的idea:你孩
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务