DP做题记录
发布日期：2021-05-09 00:16:14
浏览次数：15
分类：博客文章
本文共 360 字，大约阅读时间需要 1 分钟。
写在前面
DP能力几乎已经退化到 \(0\) 了
线性DP
CF414B Mashmokh and ACM
Solution:
设 \(f_{i, j}\) 表示选了第 \(i\) 个数，当前最大的数位 \(j\)
显然有转移方程 \(f_{i, j} = f_{i - 1, k}\) ，其中 \(k\) 是 \(j\) 的因数可以通过枚举 \(k\) 的倍数的方式来优化
P1280 尼克的任务
Solution：
设 \(f_i\) 表示 \([i,n]\) 这段时间中的最长休息时间
如果当前没有工作，那么 \(f_{i} = f_{i + 1} + 1\)否则，他必须选一个工作，\(f_{i} = \max\{f_{i + a[j].ed}\}\)，其中 \(j\) 是每项起始时间在 \(i\) 的工作
发表评论
最新留言
哈哈，博客排版真的漂亮呢~
[***.90.31.176]2025年04月08日 22时01分16秒
关于作者
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！
推荐文章
Elasticsearch Web管理工具
2019-03-06
Git 配置SSH公钥、私钥
2019-03-06
在create-react-app创建的项目下允许函数绑定运算符
2019-03-06
博客园新闻频道开始公开测试
2019-03-06
评论表聚集索引引起的评论超时问题
2019-03-06
博客园上海俱乐部4月份活动通知邀请函已经发出！
2019-03-06
Internet Explorer 10 专题上线
2019-03-06
云计算之路-阿里云上：0:25~0:40网络存储故障造成网站不能正常访问
2019-03-06
网站故障公告1：使用阿里云RDS之后一个让人欲哭无泪的下午
2019-03-06
上周热点回顾（1.21-1.27）
2019-03-06
上周热点回顾（6.3-6.9）
2019-03-06
上周热点回顾（8.12-8.18）
2019-03-06
【故障公告】升级阿里云 RDS SQL Server 实例故障经过
2019-03-06
蹒跚来迟：新版博客后台上线公测
2019-03-06
上周热点回顾（9.16-9.22）
2019-03-06
上周热点回顾（11.4-11.10）
2019-03-06
[网站公告]11月26日00:00-04:00阿里云RDS升级
2019-03-06
[网站公告]又拍云API故障造成图片无法上传（已恢复）
2019-03-06
上周热点回顾（12.16-12.22）
2019-03-06
云计算之路-阿里云上：对“黑色30秒”问题的猜想
2019-03-06
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 459533047 位访客