RainAir
My OI Blog
RainAir

动态规划
文章归档

「NOIP2017」宝藏

题目链接 Luogu P3959 这一题有两种做法:状压dp和模拟退火 解题思路 看到这一道题目的时候,我的第一反应就是:裸的Prim啊! 但仔细思考了一下,发现事情没有那么简单: 长度和层数都对后面的结果有影响,所以不能贪心的求Prim,贪心会导致局部最优…

   423   2018-11-08 去围观

斜率优化

题目链接 其实这一篇文章是为了补上一篇文章的坑…斜率优化是决策单调性优化的一中特殊形式。 题目描述 你可以连续的输出一些单词,定义每个单词的度为 $ a[i] $ ,则输出 $ i $ 到 $ j $ 的词的代价是 $(\Sigma^k _{i=1} a[i])^2 + M$。单词不能打乱顺序输出。 其…

   349   2018-09-03 去围观

决策单调性优化

写一些简单的 1D/1D 的决策单调性优化... 这种决策单调性优化的过程:列出方程 $\to$ 打表发现决策单调性 $\to$ 套单调队列/二分 我们以一些例题为例: [ZROI普转提]Bead 题目链接 注:该题有权限,看不到的就看下一题。 这一题我们推出朴素的状态转移方程: …

   305   2018-09-01 去围观

「NOIP2016」换教室

这道题甚至不如 T2 难...放在 T3 真的合适吗... 题目链接 题目描述 一张无向带权图,需要选择 $ N $ 次。每次在两个点 $ c_i,d_i $ 中,有 $ p_i $ 的概率选择点 $ d_i $,有 $ 1-p_i $ 的概率选择点 $ c_i $ ,每次选择相互独立。至多能选 $ M $ 次 $ d $ 类节点现…

   389   2018-08-17 去围观

「NOIP2017」逛公园

题意描述 给定一张无向图,定义 $ S $ 为 $ 1 $ 到 $ N $ 的最短路,求该无向图 $ 1 $ 到 $ N $ 的路径中长度小于等于 $ S+K $ 的方案。 题目链接 推荐大家去 uoj 多交一些题目,上面有很多 hack 数据。(像我之前认为 dij 就是 spfa+priority_queue)。 解题报…

   323   2018-08-03 去围观

初级的动态规划

感觉自己 dp 非常的差,于是在这里集中整理一下。 这里都是非常初级的动态规划。 定义 何为动态规划? 大概上就是一个不断探索问题性质减少那些和答案有关的值的个数。 动态规划重要的三部曲: 设计状态 考虑转移 考虑优化 由于这里是入门级别的动态规划,将…

   407   2018-07-30 去围观

「NOIP2009」最优贸易

题目链接 题目 题目描述 $ C $ 国有 $ n $ 个大城市和 $ m $ 条道路,每条道路连接这 $ n $ 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 $ m $ 条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在统计条数时也…

   273   2018-06-03 去围观

分层图最短路

定义 分层图最短路问题,一般是指我们在可以进行分层的图上进行最短路。 一般模型是: 在图上,有k次机会可以直接通过一条边,问起点与终点之间的最短路径。 题目链接 分析 其实这一题我们用动态规划的思想看,用dist[i][k]表示免费了k次的最短路径 详细的转移请参…

   386   2018-03-11 去围观

「SCOI2005」互不侵犯King

在清北学堂DP&Graph班里学到了这一题,状压DP的入门题目 题目描述 题目背景 在N×N的棋盘里面放K个King,使他们互不攻击,共有多少种摆放方案。King能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。 输入输出格式 输入格式…

   309   2018-02-09 去围观
标签
近期评论