1 条题解
-
0
题目分析
梦熊主义 题解
其实当你看到要对一个区间进行操作的时候,就要联想到区间 dp。但其实状态设计和转移也是有一定难度的
关键观察:一个 "of" 后面删除多少,与其前、后都有关,因此考虑使用区间DP。
状态设计
设
f(l,r)为闭区间[l,r]经过操作之后的最小长度。考虑转移时,我们分类讨论第一个字符是否删除:
情况1:删除第一个字符
条件:
S[l] = 'm'- 找到一个
(l,r]内的k,满足S[k] = 'x' (l,k)内的所有字符能删除,即f(l+1,k-1) = 0
转移:
含义:
- 先删除
(l,k)区间 - 然后删除
l和k及后面的K个字符 - 但不能删到负数,所以取
max{..., 0}
情况2:不删除第一个字符
条件:
- 无特殊条件,任何情况均可转移
转移:
含义:
- 因为第一个字符不删除,所以
l和(l,r]是独立的 l后面的区间最少可以剩下f(l+1,r)个字符- 再加上
l这个字符,所以总长度为f(l+1,r) + 1
答案为
f(0, n-1),其中n是字符串长度。复杂度 ,实现的时候要注意转移的顺序。
- 1
信息
- ID
- 215
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者