Codeforces 1107E. Vasya and Binary String（DP） | 张慕晖的博客 | LUX ET VERITAS
给定一个长度为n的只包含0和1的字符串，将该串中连续i个相同字符消去将得到a[i]的收益，问消去整个字符串能得到的最大收益是多少？
分析
在不会做的三道题上鸽了好久，最后还是觉得DP最好写……
这个题解[soln1]特别简明扼要，大概抓住了问题的本质，不过我可能还没有完全理解它：
- 每一个状态都可以用
[start, end, prefix]表示，其中start和end是字符串中的起始和结束index（不妨假设两端都是闭区间）（不是也行），prefix是字符串前面附加的和s[start]相等的字符的数量（包括s[start]）（不包括大概也行） - 每一个状态都有两种递推方法：
- 第一种是直接消去字符串前面附加的字符：
dp[start, end, prefix] = a[prefix] + dp[start + 1, end, 1] - 第二种是在字符串其他位置找到一个和
s[start]相同的字符，然后消去中间的字符，获得一个更大的前缀：dp[start, end, prefix] = max(dp[start+1, i-1, 1] + dp[i, end, prefix+1]) (start < i <= end, s[i] == s[start])
- 第一种是直接消去字符串前面附加的字符：
Read full article from Codeforces 1107E. Vasya and Binary String（DP） | 张慕晖的博客 | LUX ET VERITAS
No comments:
Post a Comment