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 [Pantw] |
2020-2021:teams:mian:weekly_report:2020_summer_week_5_report [2020/08/15 11:32] (当前版本) gary |
||
|---|---|---|---|
| 行 30: | 行 30: | ||
| ===== Gary ===== | ===== Gary ===== | ||
| + | |||
| + | [[http://acm.hdu.edu.cn/showproblem.php?pid=6583|HDU6583]] | ||
| + | |||
| + | * 分类：SAM，DP | ||
| + | * 题意：给定字符串 每次可以添加一个字符花费P 也可以复制前面一段花费Q 求最小构成该串的代价 | ||
| + | * 解法：考虑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.1597393216.txt.gz · 最后更改: 2020/08/14 16:20 由 grapelemonade
