标签:DP

8 篇文章

AT2702 Fountain Walk
前言 校内模拟考试的其中一题,细节很多,测的时候 WA 了几个点,后来才改对 题面 题目链接 (luogu.org/problem/AT2702) 有一个 $10^8 \times 10^8$ 的网格图,相邻格点间上下左右的距离都是 $100m$ ,格点上面有 $n$ 个圆,每个圆半径为 $10m$ ,同一行或同一列最多只有一个圆。 现在要从 $(…
2019.9.15 校内模拟赛
前言 分数不算高,100 + 37 + 0,但为什么就排到靠前了?? T1 - Snakes 原题地址 一句话题面:$n$ 个数分成 $k+1$ 组,要求每组最大值和每个值的差之和的总和最少。 挺水的一个 DP,转移有修改捕网大小和不修改两种,不修改用 ST 表求最大值记录一下最后一段的代价,修改直接转移。 $f[i][j]$ 表示当前第 $i$ …
校内 OJ 2019.5.19 模拟赛
前言 Rank 5,$130$ 分,第二题因为懒就没怎么打,第三题用玄学拿(pian)到了 $20$ 分。 P1 题面 最近几年,一场新的金融危机爆发了,这场危机使得很多人陷入的经济问题的困境。一些 X 公司的员工试图通过要求加薪度过这一难关。 X 公司有着严格的等级制度,除了公司所有者小 H 以外,其他人都有一个直属上司。没有下属的员工称为工人,…
校内OJ 2019.4.14 NOIP 模拟赛
[admonition title="注意" color="orange"]这套题目有版权,所以请不要转载题面。[/admonition] 前言 一些话 炸了,细节有很多没处理好。 题目有些不明显,丢了很多不该丢的分。 P1 质因数 题面 有一个正整数数列 $a_1,a_2,...,a_n$ 。定义函数 $f(x)$ 为 $x$ 的不同的质因数数量…
校内OJ 2019.3.17 NOIP 模拟赛
前言 Rank 7,Rating +48。 第二道题 $STL$ 莫名玄学炸 T 掉 40 分。 P1 电阻 题面 题目描述 询问要得出一个电阻值为 $\frac ab$ 的电阻。 元件由 $3$ 种方式组成: 一个电阻 一个元件与一个电阻串联 一个元件与一个电阻并联 输入格式 一行两个数, $a$ 和 $b$ 表示询问元件的阻值为 $\frac …
LOJ 10176 -「一本通 5.5 例 2」最大连续和
题面 题目传送 给你一个长度为 $n$ 的整数序列 ${a_1,a_2,\dots,a_n}$ ,要求从中找出一段连续的长度不超过 $m$ 的子序列,使得这个序列的和最大。 思路 单调队列优化 DP 模板题。 设 $t[i]$ 为 $s[1]+s[2]+\dots+s[i]$,则有状态转移方程 $f[i]=t[i]-min(t[i-1],t[i-2…
LOJ 10170 -「一本通 5.4 例 1」骑士
题面 题目传送门 在 $N*N$ 的棋盘上放 $K$ 个国王,国王可攻击相邻的 $8$ 个格子,求使它们无法互相攻击的方案总数。 思路 状压 DP 的模板,以前 DP 技能一直没怎么点,现在数据结构什么的都差不多了,开始补 DP。 预处理 对于每一行来说,我们可以用二进制来表示当前这一行的放置状态。然后再压成十进制。 然后预处理出对于一行来说的所有…