2020-2021:teams:mian:weekly_report:2020_summer_week_5_report
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:weekly_report:2020_summer_week_5_report [2020/08/14 16:20] grapelemonade [Gary] |
2020-2021:teams:mian:weekly_report:2020_summer_week_5_report [2020/08/15 11:32] (当前版本) gary |
||
|---|---|---|---|
| 行 31: | 行 31: | ||
| ===== Gary ===== | ===== Gary ===== | ||
| - | 2019hdu多校1 F | + | [[http://acm.hdu.edu.cn/showproblem.php?pid=6583|HDU6583]] |
| - | 分类：SAM，DP | + | |
| - | 题意：给定字符串 每次可以添加一个字符花费P 也可以复制前面一段花费Q 求最小构成该串的代价 | + | * 分类：SAM，DP |
| - | 解法：考虑dp过程 f(i)＝Min{f(i-1)+P,f(i-j)+Q(j满足i-j到i这一段串在之前出现过)} 考虑如何求出最大的j 可以对原串构建SAM 记录每个节点匹配的位置 如果这个位置不能满足就跳到parent节点继续匹配 全部跳的过程复杂度是O(串长) | + | * 题意：给定字符串 每次可以添加一个字符花费P 也可以复制前面一段花费Q 求最小构成该串的代价 |
| - | 评论：sam上的操作不太熟悉 写了半天才调出来 hdu上还爆栈了 | + | * 解法：考虑dp过程 f(i)＝Min{f(i-1)+P,f(i-j)+Q(j满足i-j到i这一段串在之前出现过)} 考虑如何求出最大的j 可以对原串构建SAM 记录每个节点匹配的位置 如果这个位置不能满足就跳到parent节点继续匹配 全部跳的过程复杂度是O(串长) |
| + | * 评论：sam上的操作不太熟悉 写了半天才调出来 hdu上还爆栈了 | ||
| ====== 个人训练 ====== | ====== 个人训练 ====== | ||
2020-2021/teams/mian/weekly_report/2020_summer_week_5_report.1597393247.txt.gz · 最后更改: 2020/08/14 16:20 由 grapelemonade
