这题挺多人已经补了,还是说下我对官方题解做法的理解
状态定义: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) 回帖