IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: 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 1w? 编号),游戏者占一格。开始时游戏者可以站在舞台的任意位置,手里拿着一个托盘。下图为天幕的高度为 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? 都一样。

输出格式

一个数,表示游戏者获得的最大总得分。

输入样例

3 4
1 2 3
5 2 3
6 3 4
1 1 5

输出样例

12

数据规模与约定

对于 100 % 100\% 100% 的数据, 1 ≤ w ≤ 1 0 8 1\le w\le 10^8 1w108 1 ≤ n ≤ 1 0 5 1\le n \le 10^5 1n105 1 ≤ t i ≤ 1 0 8 1\le t_i\le 10^8 1ti?108 1 ≤ p i ≤ w 1\le p_i\le w 1pi?w 1 ≤ v i ≤ 1000 1\le v_i\le 1000 1vi?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 n105,考虑优化。

显然我们可以从转移的条件 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?
a 1 = 2 × t i ? p i , a 2 = 2 × t i + p i a_1=2\times t_i-p_i,a_2=2\times t_i+p_i a1?=2×ti??pi?,a2?=2×ti?+pi?,显然我们只需要按照 a 1 a_1 a1? 或者 a 2 a_2 a2? 递增的顺序排序即可直接递推,然后问题就变成了一个类 L I S LIS LIS 问题也即二维偏序问题,使用树状数组维护最优值即可。

注意给定的 w w w 数据范围比较大,离散化即可。

时间复杂度 O ( n log ? n ) \mathcal{O}(n\log n) O(nlogn)

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7, INF = 0x3f3f3f3f;
#define lowbit(x) (x & (-x))
int n, m, s, t, w, ans;
int tr[maxn];
int f[maxn], b[maxn];

struct node {
    int x, y, t, p, v;
    bool operator < (const node &t) const {
        if (x == t.x)
            return y > t.y;

        return x < t.x;
    }
} a[maxn];

int query(int x) {
    int ans = 0;

    for (; x; x -= lowbit(x))
        ans = max(ans, tr[x]);

    return ans;
}

void update(int x, int k) {
    for (; x <= n + 1; x += lowbit(x))
        tr[x] = max(tr[x], k);
}

int main() {
    scanf("%d%d", &w, &n);
    a[0].x = a[0].y = a[0].t = -INF;

    for (int i = 1; i <= n; ++ i) {
        scanf("%d%d%d", &a[i].t, &a[i].p, &a[i].v);
        a[i].x = 2 * a[i].t + a[i].p;
        a[i].y = 2 * a[i].t - a[i].p;
    }

    sort(a, a + 1 + n);

    for (int i = 0; i <= n; ++ i)
        b[i] = a[i].y;

    sort(b, b + 1 + n);

    for (int i = 0; i <= n; ++ i)
        a[i].y = lower_bound(b, b + 1 + n, a[i].y) - b + 1;

    for (int i = 1; i <= n; ++ i) {
        f[i] = query(a[i].y) + a[i].v;
        update(a[i].y, f[i]);
    }

    for (int i = 1; i <= n; ++ i)
        ans = max(ans, f[i]);

    cout << ans << endl;
    return 0;
}

还有一种旋转坐标系的做法,这种做法暂时没太看懂…

https://www.cnblogs.com/onglublog/p/11325459.html
在这里插入图片描述

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-09-03 12:10:17  更:2021-09-03 12:10:38 
 
开发: 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-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码