| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> BZOJ 2131 免费的馅饼(DP,二维偏序问题 / 旋转坐标轴转化问题)【BZOJ 修复工程】 -> 正文阅读 |
|
[数据结构与算法]BZOJ 2131 免费的馅饼(DP,二维偏序问题 / 旋转坐标轴转化问题)【BZOJ 修复工程】 |
整理的算法模板合集: ACM模板
题目链接https://hydro.ac/d/bzoj/p/2131 是 hydro 的 BZOJ 修复工程 !(我也去领了一点题慢慢修着玩,这题就是我修的嘿嘿嘿) 题目描述SERKOI 最新推出了一种叫做 “免费馅饼” 的游戏:游戏在一个舞台上进行。舞台的宽度为 w w w?? 格(从左到右依次用 1 ~ w 1\sim w 1~w? 编号),游戏者占一格。开始时游戏者可以站在舞台的任意位置,手里拿着一个托盘。下图为天幕的高度为 4 4 4 格时某一个时刻游戏者接馅饼的情景。 游戏开始后,从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或者向右移动一格或两格,也可以以站在原地不动。 当馅饼在某一时刻恰好到达游戏者所在的格子中,游戏者就收集到了这块馅饼。当馅饼落在一个游戏者不在的格子里时该馅饼就消失。 写一个程序,帮助我们的游戏者收集馅饼,使得所收集馅饼的分数之和最大。 输入格式第一行是用空格隔开的两个正整数,分别给出了舞台的宽度 w w w 和馅饼的个数 n n n。 接下来 n n n 行,每一行给出了一块馅饼的信息。由三个正整数组成,分别表示了每个馅饼落到舞台上的时刻 t i t_i ti?,掉到舞台上的格子的编号 p i p_i pi?,以及分值 v i v_i vi?。 游戏开始时刻为 0 0 0 。输入文件中同一行相邻两项之间用一个空格隔开。输入数据中可能存在两个馅饼的 t i t_i ti? 和 p i p_i pi? 都一样。 输出格式一个数,表示游戏者获得的最大总得分。 输入样例
输出样例
数据规模与约定对于 100 % 100\% 100% 的数据, 1 ≤ w ≤ 1 0 8 1\le w\le 10^8 1≤w≤108, 1 ≤ n ≤ 1 0 5 1\le n \le 10^5 1≤n≤105, 1 ≤ t i ≤ 1 0 8 1\le t_i\le 10^8 1≤ti?≤108, 1 ≤ p i ≤ w 1\le p_i\le w 1≤pi?≤w, 1 ≤ v i ≤ 1000 1\le v_i\le 1000 1≤vi?≤1000 Solution 比较简单的一道题。 显然考虑 DP 。 设 f [ i ] f[i] f[i] 表示接住第 i i i 个馅饼以后能获得的最大的分数。 显然有转移方程: f [ i ] = max ? { f [ j ] ∣ ∣ p i ? p j ∣ ≤ 2 × ( t i ? t j ) } + v i f[i] = \max\{f[j]\mid |p_i-p_j|\le 2\times (t_i-t_j)\} + v_i f[i]=max{f[j]∣∣pi??pj?∣≤2×(ti??tj?)}+vi? 直接转移显然是 O ( n 2 ) O(n^2) O(n2) 的, n ≤ 1 0 5 n\le 10^5 n≤105,考虑优化。 显然我们可以从转移的条件 j j j 入手。对于每一个可以转移到 i i i 的 j j j ,需要满足 ∣ p i ? p j ∣ ≤ 2 × ( t i ? t j ) |p_i-p_j|\le 2\times (t_i-t_j) ∣pi??pj?∣≤2×(ti??tj?),展开后有:
∣
p
i
?
p
j
∣
≤
2
×
(
t
i
?
t
j
)
?
2
×
(
t
i
?
t
j
)
≤
p
i
?
p
j
≤
2
×
(
t
i
?
t
j
)
2
×
t
i
?
p
i
≥
2
×
t
j
?
p
j
?
o
r
?
2
×
t
i
+
p
i
≥
2
×
t
j
+
p
j
|p_i-p_j|\le 2\times (t_i-t_j)\\ -2\times( t_i-t_j)\le p_i-p_j\le 2\times (t_i-t_j)\\ 2\times t_i-p_i\ge 2\times t_j-p_j\ \mathrm{or}\ 2\times t_i+p_i\ge 2\times t_j+p_j
∣pi??pj?∣≤2×(ti??tj?)?2×(ti??tj?)≤pi??pj?≤2×(ti??tj?)2×ti??pi?≥2×tj??pj??or?2×ti?+pi?≥2×tj?+pj? 注意给定的 w w w 数据范围比较大,离散化即可。 时间复杂度 O ( n log ? n ) \mathcal{O}(n\log n) O(nlogn) Code
还有一种旋转坐标系的做法,这种做法暂时没太看懂… |
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 | -2024/11/26 1:25:32- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |