竞赛讨论区 > 多校(第一场)E-Removal
头像
CToshi
编辑于 2018-07-21 11:09
+ 关注

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


全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐