2020-2021:teams:mian:weekly_report:2020_summer_week_8_report
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:mian:weekly_report:2020_summer_week_8_report [2020/09/04 15:20] gary |
2020-2021:teams:mian:weekly_report:2020_summer_week_8_report [2020/09/04 15:20] (当前版本) gary [Gary] |
||
|---|---|---|---|
| 行 28: | 行 28: | ||
| * 分类：DP | * 分类：DP | ||
| * 题意：一个01串，每次删去任意相邻两数中的较小数，最多删n-1，问可以得到哪些子串 | * 题意：一个01串，每次删去任意相邻两数中的较小数，最多删n-1，问可以得到哪些子串 | ||
| - | * 做法：记f[i]表示原串匹配到第i位并且选了第i位的方案数，枚举下一位选0或1，选1则选择距离最近的1，选0则要保证前面已经选的0和接下来的再选的0是连续的，记录每一段之前连续零个数以及之后的比连续零个数多1的位置即可，统计只需要统计 | + | * 做法：记f[i]表示原串匹配到第i位并且选了第i位的方案数，枚举下一位选0或1，选1则选择距离最近的1，选0则要保证前面已经选的0和接下来的再选的0是连续的，记录每一段之前连续零个数以及之后的比连续零个数多1的位置即可，统计只需要统计f[1~n]中末尾可以选为该位的项之和 |
| - | f[1~n]中末尾可以选为该位的项之和 | + | |
| * 评论：对0的转移比较妙 | * 评论：对0的转移比较妙 | ||
2020-2021/teams/mian/weekly_report/2020_summer_week_8_report.1599204022.txt.gz · 最后更改: 2020/09/04 15:20 由 gary
