泪痕@一语成谶
辗转当作浮生妖,流离惊似尘世鬼
[NOIP2012] 开车旅行 [NOIP2012] 开车旅行
摘要 倍增优化 DP 小 A 和小 B 决定旅行,城市从 1 到 N 编号,编号较小的城市在编号较大的城市的西边,各个城市的海拔高度互不相同,记城市 i 的海拔高度为 ,城市 i 和城市 j 之间的距离 $d[i,j]=|H_
2019.06.13
[POI2013]BAJ-Bytecomputer [POI2013]BAJ-Bytecomputer
摘要 题意:一个序列只有 ,每次可以选一个 使 ,求操作最少次数使得整个序列非严格单调递增. 小清新的 DP 题~ #include<bits/stdc++.h>
2019.04.03
[POI2010]PIL-Pilots [POI2010]PIL-Pilots
摘要 近期以 POI 的题为主,因为小清新~ 题意:给定 n,k 和一个长度为 n 的序列,求最长的最大值最小值相差不超过 k 的子串 最大最小就是单调队列啦,又因为是找连续子串的最大长度,显然就是尺取法的思路,每次纳入一个新的元素时更新
2019.04.02
DP 优化微剖 2 DP 优化微剖 2
引言和《鹰蛋》一样的优化思路 书稿复制 - 问题引入对于长度为 的序列序列 ,要求将其分为 段,使得每一段的和的最大值最小 DP 思路 表示前 个数分 段的最小最大值,记 $S[k]=
2019.01.24
DP 优化微剖 DP 优化微剖
引言学习朱晨光《从《鹰蛋》一题浅析对动态规划算法的优化》的笔记 鹰蛋问题引入有一堆共 M 个鹰蛋,一位教授想研究这些鹰蛋的坚硬度 E。 他是通过不断 从一幢 N 层的楼上向下扔鹰蛋来确定 E 的。当鹰蛋从第 E 层楼及以下楼层落下时是不会
2019.01.21
[SCOI2010] 股票交易 [SCOI2010] 股票交易
题意对于一个股市,给出第 天买 / 卖股票的价格和买 / 卖股票的数量,依次为 . 并要求手上的股票数不超过 ,两次交易的间隔时间至少 天(买卖都各算一次交易),初始时有
2019.01.16
[HAOI2010] 软件安装 [HAOI2010] 软件安装
题意有 个软件和空间为 的硬盘,每个软件有一个占用空间 和价值 和一个依赖软件 表示没有依赖)。一个软件要安装,仅当其依赖软件已安装且硬盘空间足够,求最大价值. $N\le
2019.01.16
[HAOI2011]Problem A [HAOI2011]Problem A
题意一次考试共有 个人参加,第 个人说:“有 个人分数比我高, 个人分数比我低。” 问最少有几个人没有说真话(可能有相同的分数) . 分
2019.01.16
斜率优化 DP 入门 斜率优化 DP 入门
前言本蒟蒻的第一道斜率优化 DP 前后卡了 3 小时…… 海星 有时候好不容易推出一个 DP 的式子,结果发现数据范围太大? 单调队列无法优化? 那就考虑斜率优化吧 [APIO2014] 序列分割 你正在玩一个关于长度为 的非负整
2019.01.15
[USACO12MAR] 花盆 [USACO12MAR] 花盆
题意给定 n 个点 和一个整数 ,求一个最小区间 ,使得点集 中的纵坐标的极差 最大. 输出区间长度 . $n\leq 10^5,x
2019.01.15
[LuoguP1357] 花园 [LuoguP1357] 花园
暴力 DP首先有一个暴力状压 DP, 表示以第 个花盆结尾,后 个花盆的二进制状态为 (1 为 C,0 为 P)时的方案数 对于环形的处理,我们让两个相同状态作为 DP 的初始和结尾即可.具体的说,初始
2018.12.17
[SDOI2010] 地精部落 [SDOI2010] 地精部落
题意问 1-n 的排列中,峰谷交替的排列有多少个,答案对 P 取模。 峰谷交替:即对于一个排列中的任意一个数 ,满足以下条件之一: a_{i-1}>a_i using namespace std; const int N=420
2018.12.15
[SCOI2005] 最大子矩阵 [SCOI2005] 最大子矩阵
题意矩形的每一个格子有权值 一个宽 1 或 2 的矩形选出 k 个子矩形,问最大权值和 分析既然宽度只有 2, 状压一下每行状态 DP 即可 定义 表示前 行选 个子矩形的最大权值. 其中 k: k=
2018.12.13
[HAOI2007] 理想的正方形 [HAOI2007] 理想的正方形
题意有一个 的整数组成的矩阵,现请你从中找出一个 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。 分析好多人用什么倍增的算法,还有用线段树的。。。 我们考虑一下,要求以 $(i
2018.12.08
[AHOI2009] 中国象棋 [AHOI2009] 中国象棋
分析计数 DP 三进制状压 DP 可以拿 50 分 考虑到我们并不需要记录每一列的相对位置 定义 表示前 行中有 列放了 1 个棋子, 列放 2 个棋子的方方案数 采用刷表法,对于 $f[i,j,
2018.11.18
[ZJOI2005] 午餐 [ZJOI2005] 午餐
分析DP& 贪心 首先贪心地想到,让吃饭时间长的先排队(邻项微扰证明) 定义 表示前 i 个人,1 号窗口打饭总时间为 时的最早吃完饭的时间。 当第 个人在 1 号窗口时,吃完饭的时间为 $max
2018.11.18
[ZJOI2007] 棋盘制作 [ZJOI2007] 棋盘制作
悬线法。以每一个点向上达到的最长的长度作为悬线,左右扫,记录可以到达的最左边的长度以及最右边的长度,再以此更新答案即可。 更具体的, 表示从 往上最长的黑白相间的格子的高度; 表示从
2018.11.17
状态压缩动态规划 状态压缩动态规划
引言状压 DP,是一种动态规划。一般的动态规划状态简单,通常一两个维度就能搞定。不过当状态过于复杂时,简单的维度将无法表示状态,而过多的维度将加大复杂度,于是,就有了状压 DP 的出现。 状态压缩状压 DP 的要点,就是状态压缩。状态压缩
2018.11.16
数位动态规划 数位动态规划
概述数位 DP 的基本思想就是按位 DP,对数字的每一位做 DP。 数位 DP 常用于求解区间内满足条件的数的计数问题。 数位 DP 的一个重要特征是多维度。事实上由于在数位 DP 的过程中有若干限制条件,使得问题的维度较多,因此相比普通
2018.11.16
[HDU2196]Computer [HDU2196]Computer
二次扫描与换根法这种算法通常用于统计无根树上每个结点的答案,并且对于根结点的答案容易统计的题目。这时,我们就把每个结点在 DFS 遍历的同时换作根,同时统计答案。 我们对整棵树做 2 次 dfs: 第一次: 选定一个结点为根(比如 1 号)
2018.11.08
1 / 2