多校(第一场)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

相关推荐

不愿透露姓名的神秘牛友
07-04 18:25
点赞 评论 收藏
分享
ZywOo_求职版:谁问你了....
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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